Processing math: 100%
编程题
                ### 问题描述

卓儿住在一个橙树附近,她调查橙子。橙树上的橙子可以有多达 5×50 种橙色。她从一个橙子走到另一个橙子,检查橙树的不同特性。橙子是由树枝连接在一起的。橙子的数量比树枝多,但仍然可以通过树枝从任何一个橙子到达另一个橙子。这棵树是有根的。

卓儿有很多问题,形式如下:她从橙子 A 通过最短路径到橙子 B,并想知道最短路径上所有边的所有子树中不同橙色的总数。

输入格式

第一行包含三个整数 NQR,表示橙子的数量,问题的数量和根的数量。

接下来的一行包含 N 个整数 Si,表示橙子 i 的橙色。

接下来的 N1 行包含两个整数 ab,连接在树枝上的橙子的编号。

接下来的 Q 行包含两个整数 AB,表示卓儿感兴趣的路径。

输出格式

对于每个问题,回答从 AB 的最短路径上所有节点的所有子树中橙色的数量。

样例输入

10 7 1
1 2 1 4 5 6 6 8 9 9
0 9
9 3
3 4
4 6
4 5
4 8
1 3
1 2
2 7
4 4
8 6
0 6
7 0
7 2
0 0
2 3

样例输出

3
3
5
7
2
1
7

评测数据规模

1N,Q1040RN11Si2500a,bN10A,BN1

查看答案
赣ICP备20007335号-2