15899번 - 트리와 색깔

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⁵), 질의의 개수를 나타내는 M(1 ≤ M ≤ 2×10⁵), 정점의 색깔 종류를 나타내는 C(1 ≤ C ≤ N)가 공백 하나를 사이에 두고 차례로 주어진다.

두 번째 줄에는 각 정점의 색깔을 나타내는 N개의 정수가 공백으로 구분되어 순서대로 주어진다. 첫 번째 수는 1번 정점의 색깔이며, ..., 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로 나눈 나머지를 출력한다.