News#10953
Deni is the boss of a company with workers, numbered from 1 to . The company structure is strictly hierarchical – every worker (except number 1) has exactly one direct supervisor. So, every worker has 1 or more subordinates (direct and indirect) including himself. For example, worker 1 has exactly subordinates, including himself. Of course, there isn't a situation where some subordinate of a worker is his direct supervisor. For some worker , we will call a 0-level subordinate. Then, his direct subordinates will be called 1-level subordinates of . All of their direct subordinates (which are indirect subordinates of ) will be called 2-level subordinates of and so on.
There is a breaking piece of news that is known by some of the workers. Deni wants to inform all of the company employees. So, multiple times she chooses worker and number , and tells the news to all 0-level, 1-level (if they exist), ..., -level (if they exist) subordinates of . We will call all these subordinates, -subordinates of . The problem with this type of announcement is that most of the time, many chosen subordinates already know the piece of news. That's why Deni wants a system that can tell her the number of workers among all the -subordinates of that have already learned about the news. Write a program news that can help her.
From the first line of the standard input read one integer – the number of workers in Deni's company. From each of the next N-1 lines read two integers and , which show that the worker is a direct subordinate to the worker . From the next line read integers: b_{1}, b_{2}, \ldots, b_{N}, where b_{i} is 1, if the worker knows the news at the beginning and 0 otherwise. From the next line read one integer – the number of queries. From each of the last lines, read queries of two types:
type 1 (news announcement query): – Deni tells the news to all the -subordinates of
type 2 (question query): – Deni asks for the number of the workers that know the news among the -subordinates of
For every query of type 2, on separate lines in the same order as in the input, write one integer – the answer for the corresponding question.
Exemple 1
The above picture shows the hierarchy of the company and the workers that know the news at the beginning are colored in orange.
For the first query 2 4 4:
The 0-level subordinate of worker 4 is 4, the 1-level subordinates of worker 4 are workers 7 and 8, the 2-level subordinates of worker 4 are 9 and 10 and there are no 3-level and 4-level subordinates of worker 4. Workers 4, 8 and 10 know the news, so the answer to this question query is 3.
For query 1 4 1:
The 1-subordinates of worker 4 are workers 4, 7 and 8. Workers 4 and 8 already know the news, so only worker 7 learns the news at this time.
For the second query 2 4 4:
The 4-subordinates of worker 4 are 4, 7, 8, 9 and 10. Workers 4, 7, 8 and 10 know the news, so the answer to the query this time is 4.
2 \leq N \leq 2 \times 10^{5}
1 \leq Q \leq 2 \times 10^{5}
0 \leq k \leq N
Subtask | Points | Further constraints | ||
1 | 0 | – | – | The example. |
2 | 11 | \leq 10^{4} | \leq 10^{4} | – |
3 | 15 | \leq 2 \times 10^{5} | \leq 2 \times 10^{5} | In all queries: k = N. |
4 | 17 | \leq 2 \times 10^{5} | \leq 2 \times 10^{5} | There are no queries of type 1. |
5 | 26 | \leq 5 \times 10^{4} | \leq 5 \times 10^{4} | – |
6 | 31 | \leq 2 \times 10^{5} | \leq 2 \times 10^{5} | – |
The points for a subtask are given only if all the tests for the subtask are successfully passed.