페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3602

트리와 색깔 2s 128MB

문제

1부터 N까지의 번호가 부여된 N개의 정점과 N-1개의 간선으로 구성된 트리가 있다. 이 트리의 루트는 1번 정점이며, 임의의 한 정점과 다른 정점 사이의 경로가 반드시 한 개 존재한다.

트리의 각 정점은 특정 색깔을 가지고 있다. 편의상 색깔은 1 이상 C 이하의 자연수로 표현된다.

이때, 질의 f(v, c)를 다음과 같이 정의하자.

  • f(v, c) : 정점 v가 루트인 부트리(sub-tree)에서 색깔이 c 이하인 정점의 개수

M개의 질의 f(v_i, c_i)가 주어질 때, 각 질의에 대한 답을 계산하는 프로그램을 작성하시오.


입력

첫 번째 줄에 정점의 수를 나타내는 N(1 ≤ N ≤ 2×10^5), 질의의 개수를 나타내는 M(1 ≤ M ≤ 2×10^5), 정점의 색깔 종류를 나타내는 C(1 ≤ C ≤ N)가 공백 하나를 사이에 두고 차례로 주어진다.

두 번째 줄에는 각 정점의 색깔을 나타내는 N개의 정수가 공백으로 구분되어 순서대로 주어진다. 첫 번째 수는 1번 정점의 색깔이며, \cdots , N 번째 수는 N번 정점의 색깔이다.

세 번째 줄부터 N-1개의 줄에 걸쳐서 트리를 이루는 각 간선의 정보가 주어진다. 각 간선의 정보는 해당 간선을 이루는 서로 다른 두 정점의 번호로 구성된다. 각 정점의 번호는 1 이상 N 이하의 자연수이다.

이후, 이어서 M개의 줄에 걸쳐서 i번째 줄에 i번째 질의의 정보 v_i, c_i가 공백으로 구분되어 주어진다. v_i는 1 이상 N 이하의 정점 번호를 나타낸다. c_i는 1 이상 C 이하의 색깔 정보를 나타낸다.


출력

M개의 질의에 대한 정답을 모두 더한 뒤, 1,000,000,007로 나눈 나머지를 출력한다. 


예제 #1

5 5 3

1 2 1 3 3

1 2

2 3

3 4

4 5

1 1

1 3

3 2

4 3

5 3
11

예제 #2

4 2 2

1 2 2 2

1 2

1 3

1 4

1 1

1 2
5


출처

UCPC 2018
로그인해야 코드를 작성할 수 있어요.