P5901 [IOI 2009] Regions

### Abuse of this problem’s judging will result in account suspension. IOI 2009 D2T3. The original time limit was 8 s. To save judging resources, the time limit has been changed to 4 s.

The United Nations Regional Development Agency (UNRDA) has a well-organized structure. It employs $N$ commissioners, and each commissioner belongs to one of several regions. The commissioners are numbered from $1$ to $N$ according to seniority, where commissioner $1$ is the chairperson and has the highest seniority. The regions are numbered from $1$ to $R$. Every commissioner except the chairperson has a direct mentor. Any direct mentor has higher seniority than the commissioner they mentor. We say that commissioner $A$ is a mentor of commissioner $B$ if and only if $A$ is the direct mentor of $B$, or $A$ is a mentor of the direct mentor of $B$. Clearly, the chairperson is a mentor of every other commissioner, and no two commissioners are mentors of each other. Now, to investigate many accusations that UNRDA is biased toward certain regions due to an unbalanced organizational structure, UNRDA wants to build a computer system: given the direct mentor relationships between commissioners, the system can answer queries of the following form. Given two regions $r_1$ and $r_2$, the system should answer how many pairs of commissioners $e_1$ and $e_2$ satisfy: $e_1$ belongs to $r_1$, $e_2$ belongs to $r_2$, and $e_1$ is a mentor of $e_2$. Each query has two parameters $r_1$ and $r_2$, and the result is an integer: the number of ordered pairs $(e_1, e_2)$ satisfying the conditions above. **Task**: Write a program that, given each commissioner’s region and direct mentor, answers the queries above **online**. **Forced online will be conducted in an interactive format**.

The first line contains three integers $N, R, Q$, separated by a single space, representing the number of employees, the number of regions, and the number of queries. The next $N$ lines give the description of the $N$ commissioners in order of seniority. Line $k$ describes commissioner number $k$. The first line (the one describing the chairperson) contains one integer: the region $H_1$ to which the chairperson belongs. Each of the remaining $N - 1$ lines contains two integers separated by a single space, representing the direct mentor $S_k$ of commissioner $k$ and the region $H_k$ to which commissioner $k$ belongs. ### Interactive Format After reading all input data, your program must then read the queries one by one from standard input, and output the answers to standard output. You must answer exactly $Q$ queries, one at a time. **Before reading the next query, you must answer the current query first**. Each query is one line from standard input, containing two distinct integers $r_1, r_2$.

For each query, output one line to standard output containing one integer: the number of pairs of commissioners $e_1$ and $e_2$ in UNRDA that satisfy the following conditions: $e_1$ belongs to region $r_1$, $e_2$ belongs to region $r_2$, and $e_1$ is a mentor of $e_2$. **Note**: The input guarantees that the correct answer for any query is less than $10 ^ 9$. **Special note**: To interact correctly with the interactive library, your program must **flush the standard output buffer after answering each query**. You also need to avoid accidentally blocking when reading from standard input, which may happen if you use a statement like `scanf("%d\n", ...)`. You may use the following statements to flush the buffer: - For C/C++: `fflush(stdout)`; - For C++: `std::cout

### Constraints and Notes - For $30\%$ of the testdata, $N \leq 500$. - For $55\%$ of the testdata, no region contains more than $500$ commissioners. - $15\%$ of the testdata satisfies both conditions above, and $70\%$ of the testdata satisfies at least one of the conditions above. - For $100\%$ of the testdata, $1 \le N, Q \le 2 \times 10^5$, $1 \le H_k, r_1, r_2 \le R \le 2.5 \times 10^4$, $1 \le S_k < k$. Translated by ChatGPT 5