Problem G: G: 零食采购

上一题 正确率: $100.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 n 颗星 球，由 n − 1 条航路连接为连通图，第 i 颗星球卖第 ci 种零食特产。小蓝想出 了 q 个采购方案，第 i 个方案的起点为星球 si ，终点为星球 ti ，对于每种采购 方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的 零食（包括起点终点），请计算每种采购方案最多能买多少种不同的零食。 

Input

输入的第一行包含两个正整数 n, q ，用一个空格分隔。 

第二行包含 n 个整数 c1, c2, · · · , cn ，相邻整数之间使用一个空格分隔。

 接下来 n − 1 行，第 i 行包含两个整数 ui , vi ，用一个空格分隔，表示一条 航路将星球 ui 与 vi 相连。

 接下来 q 行，第 i 行包含两个整数 si , ti ，用一个空格分隔，表示一个采购 方案。

Output

输出 q 行，每行包含一个整数，依次表示每个采购方案的答案。

Sample Input复制

4 2
1 2 3 1
1 2
1 3
2 4
4 3
1

Sample Output复制

3
2

提示

第一个方案路线为 {4, 2, 1, 3} ，可以买到第 1, 2, 3 种零食； 

第二个方案路线为 {1, 2, 4} ，可以买到第 1, 2 种零食。

【评测用例规模与约定】 

对于 20% 的评测用例，1 ≤ n, q ≤ 5000 ； 对于所有评测用例，1 ≤ n, q ≤ 105，1 ≤ ci ≤ 20，1 ≤ ui , vi ≤ n，1 ≤ si , ti ≤ n。