P5901 [IOI 2009] Regions

## 滥用本题评测将被封号 IOI2009 D2T3 原题时间限制 8s，为节约评测资源，时间限制改为 4s。

联合国区域发展委员会（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)$ 二元组的数量。 **任务**：编写一个程序，给定每个委员的地区和直接导师，**在线** 回答上述询问。 **强制在线将以交互的格式进行**。

无

无

### 数据范围与约定 - 对于 $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$。