OI题库

问题描述

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

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

  现在，联合国区域发展委员会想要建立一个计算机系统：在给定委员之间的直接导师关系的情况下，该系统可以自动地回答下述形式的问题：给定两个地区r1和r2，要求系统回答委员会中有多少对委员e1和e2，满足e，属于r1而e2属于r2，并且e1是e2的导师。

    任务

    写一个程序，给定所有委员所属的地区和委员之间的直接导师关系，逐一回答上述的查询问题。   

    数据规模  

    1≤N≤200，000    委员的数目   

    1≤R≤25，000    地区的数目   

    1≤Q≤200，000    你的程序需要回答的查询的数目   

    1≤Hk≤R    委员k所属的地区(1≤k≤N)   

    1≤Sk≤k    委员k的直接导师(2≤k≤N)   

    1≤r1，r2≤R    查询所给出的地区   

    输入   

    你的程序需要从标准输入读入下列数据：   

    第一行依次包含整数N，R和Q，分别以一个空格隔开。   

    接下来N行按照资历的顺序给出了N个委员的描述信息。这N行中的第k^th行描述了编号为k的委员。第一行(描述主席的一行)包含一个整数：主席所属的地区H1；其余的N-1行每行包含两个整数(以一个空格隔开)分别表示委员k的直接导师Sk和委员k所属的地区Hk。

 

    每个查询是标准输入的一行，包含两个不同的整数，以一个空格隔开：表示地区r1和r2。

    对查询的回答是标准输出的一行，包含一个整数，表示在联合国区域发展委员会中有多少对委员e1和e2满足下述条件，即e1属于地区r1，e2属于地区r2，并且e1是e2的导师。

    注意：所有给出的查询语句的正确答案都小于1，000，000，000。

     评分说明

    有30分的评测数据，R不超过500。

    有55分的评测数据，没有任何地区的委员数目超过500。

    有15分的评测数据，同时满足上述两个条件。

有70分的评测数据，满足上述两个条件中的至少一个。

样例

输入样例

6 3 4

1

1 2

1 3

2 3

2 3

5 1

1 2

1 3

2 3

3 1

输出样例

1 

3 

2 

1    

  关于测试

  如果你想在比赛系统的测试界面测试你的程序，你提供的输入文件必须包含与上述样例格式相同的输入数据和所有查询语句。