|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초 (추가 시간 없음)||1024 MB||157||51||41||28.671%|
In RUN-land, there are $n$ cities numbered $1$ to $n$. Some pairs of cities are connected by a bidirectional road. It happens that there are $n-1$ roads in total and that for any two cities, and there is a unique path from one to the other.
The city number $1$ is the capital. Initially all roads have no color. Alex, the king of RUN-land asks you to perform the following query $Q$ times.
Given $Q$ queries in total, compute the answer for the second part of each query.
The first line of the input contains three integers $n,\ C,\ Q$ ($1\leq n,\ C,\ Q\leq 200,000$), separated by a single space, which are the number of cities in RUN-land, the number of possible colors, and the number of queries, respectively. Each of the next $n-1$ lines contains two integers $u,\ v$ ($1\leq u,\ v\leq n$) meaning that there is a bidirectional road directly connecting the cities numbered $u$ and $v$.
Each of the next $Q$ lines contains a query, which contains $3$ integers $u,\ c,\ m$ as described in the statement. ($1\leq u\leq n$, $1\leq c\leq C$, $0\leq m\leq n-1$)
Print $Q$ lines, one for each query. Each line must contain one integer, the answer to the corresponding query.
6 5 5 1 3 2 3 1 4 6 3 5 2 5 1 3 6 2 2 2 3 1 4 4 1 1 5 0
1 2 2 3 1
The answer for the last query is $1$ since color $5$ is used in $0$ roads.