#3351. [ioi2009]Regions

题目描述

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  

数据范围与提示