区域发展

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 region.in 输出文件 region.out

问题描述

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

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

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

    任务

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

    数据规模  

    1N200000    委员的数目   

    1R25000    地区的数目   

    1Q200000    你的程序需要回答的查询的数目   

    1HkR    委员k所属的地区(1kN)   

    1Skk    委员k的直接导师(2kN)   

    1r1r2R    查询所给出的地区   

    输入   

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

    第一行依次包含整数NRQ,分别以一个空格隔开。   

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

 

    每个查询是标准输入的一行,包含两个不同的整数,以一个空格隔开:表示地区r1r2

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

    注意:所有给出的查询语句的正确答案都小于1000000000

     评分说明

    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

输出样例

3 

2 

1    

  关于测试

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