[IOI2009] Regions

题目描述

联合国区域发展委员会（The United Nations Regional Development Agency, UNRDA）有一个良好的组织结构。它任用了 $N$ 名委员，每名委员都属于几个地区中的一个。委员们按照其资历被编号为 $1$ 到 $N$ ，$1$ 号委员是主席，资历最高。委员所属地区被编号为 $1$ 到 $R$。除了主席之外所有委员都有一个直接导师。任何直接导师的资历都比他所指导的委员的资历要高。

我们称委员 $A$ 是委员 $B$ 的导师当且仅当 $A$ 是 $B$ 的直接导师或者 $A$ 是 $B$ 的直接导师的导师。显然，主席是所有其他委员的导师，没有任何两名委员互为导师。

现在，为了调查大量对 UNRDA 偏向某些地区的不平衡的组织结构的指控，UNRDA 想要建立一个计算机系统：在给定委员之间的直接导师关系的情况下，该系统可以回答下述形式的问题：给定两个地区 $r_1$ 和 $r_2$，要求系统回答委员会中有多少对委员 $e_1$ 和 $e_2$，满足 $e_1$ 属于 $r_1$，而 $e_2$ 属于 $r_2$，并且 $e_1$ 是 $e_2$ 的导师。每次询问都有两个参数 $r_1$ 和 $r_2$，结果是一个整数：满足上述条件的 $(e_1, e_2)$ 二元组的数量。

任务：编写一个程序，给定每个委员的地区和直接导师，在线 回答上述询问。

强制在线将以交互的格式进行。

输入格式

第一行包含三个整数 $N, R, Q$，分别由一个空格隔开，分别表示雇员人数，区域数和查询数。

接下来 $N$ 行按照资历的顺序给出了 $N$ 个委员的描述信息。其中第 $k$ 行描述了编号为 $k$ 的委员。第一行（描述主席的一行）包含一个整数：主席所属的地区 $H_1$。其余的 $N - 1$ 行，每行包含两个整数，以一个空格隔开分别表示委员 $k$ 的直接导师 $S_k$ 和委员 $k$ 所属的地区 $H_k$。

交互格式

在读入所有输入数据之后，你的程序必须依次从标准输入中读入询问，并将询问结果输出至标准输出。必须依次回答 $Q$ 个询问，每次回答一个。在读入下一个询问之前，你必须先回答当前询问。

每个询问是标准输入的一行，用两个不同整数 $r_1, r_2$ 表示。

输出格式

对查询的回答是标准输出的一行，包含一个整数，表示在 UNRDA 中有多少对委员 $e_1$ 和 $e_2$ 满足下述条件：$e_1$ 属于地区 $r_1$，$e_2$ 属于地区 $r_2$，并且 $e_1$ 是 $e_2$ 的导师。

注意：输入数据保证给出的任意询问的正确答案小于 $10 ^ 9$。

特别注意：为了正确地和交互库交互，你的程序必须 在回答每次询问后刷新标准输出缓冲区。你同样需要避免意外地在读入标准输入时堵住了输入流，这有可能在你使用 scanf("%d\n", ...) 的语句时发生。

你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。

样例 #1

样例输入 #1

6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2

1 3

2 3

3 1

样例输出 #1

1 [刷新缓冲区]

3 [刷新缓冲区]

2 [刷新缓冲区]

1 [刷新缓冲区]

提示

数据范围与约定

• 对于 $30\%$ 的数据，$N\leq 500$。
• 对于 $55\%$ 的数据，没有地区包含超过 $500$ 个委员。
• 同时满足上述两个条件的数据有 $15\%$，至少满足上述一个条件的数据有 $70\%$。
• 对于 $100\%$ 的数据，$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$。