#3351. [ioi2009]Regions

内存限制:128 MiB 时间限制:120 Sec

题目描述

 

N个节点的树,有R种属性,每个点属于一种属性。有Q次询问,每次询问r1,r2,回答有多少对(e1,e2)满足e1属性是r1,e2属性是r2,e1是e2的祖先。
数据规模
N≤200000,R≤25000,Q≤200000
30%数据R≤500
55%数据同种属性节点个数≤500

输入格式

输出格式

样例

样例输入


			
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

数据范围与提示