[I] 攻城

题目背景

> “~~将军~~ WJJ 百战死,~~壮士~~ WJJ 十年归。” $\mathrm{WJJ}$ 初中大佬,$\mathrm{WJJ\ TQL!!!}$

题目描述

敌对的城楼共有 $n$ 座,每座城楼有一个表示颜色的值 $color_i$。 城楼之间由 $n-1$ 条双向道路连接,保证不会有回路。 $\mathrm{WJJ}$ 共接到了 $m$ 个任务,每个任务给定一个出发点 $x$ 和 结束点 $y$。 这表示 $\mathrm{WJJ}$ 需要从城楼 $x$ 开始,走最短路径到城楼 $y$,并攻下路径上所有的城楼。 任务之间互不影响,即如果两个任务包含同样的城楼也需要重复攻击。 由于这些任务对于 $\mathrm{WJJ}$ 大爷不费吹灰之力,所以 $\mathrm{WJJ}$ 每次攻城的时候会顺便统计此行攻下的城楼中出现次数最多的颜色。

输入输出格式

输入格式


第一行,一个数 $n$,表示城楼的个数。 第二行,$n$ 个整数 $color_i$,表示各个城楼的颜色。 以下 $n-1$ 行,每行两个整数 $u,v$,表示有一条双向道路连接城楼 $u$ 和 $v$(城楼编号为 $1 \dots n$)。 第 $2+n$ 行,一个整数 $m$,表示任务的个数。 以下 $m$ 行,每行两个整数 $x,y$。

输出格式


$m$ 行,每行一个整数,表示每个任务中出现次数最多的颜色,如果有多个颜色出现次数相同取最小值,按照读入的顺序输出。

输入输出样例

输入样例 #1

7
3 3 2 2 1 1 1
1 2
2 3
2 4
1 5
5 6
6 7
5
3 3
3 4
3 7
4 5
4 6

输出样例 #1

2
2
1
3
1

说明

样例中给定的城楼情况如下: ![](https://i.loli.net/2018/09/16/5b9e2939ac7f5.png) ### 第一个询问 只攻下一个城楼,答案为上图中的黄色($2$)。 ### 第二个询问 ![](https://i.loli.net/2018/09/16/5b9e29b2d53ef.png) 答案为黄色($2$)。 ### 第三个询问 ![](https://i.loli.net/2018/09/16/5b9e2a05714ab.png) 答案为蓝色($1$)。 ### 第四个询问 ![](https://i.loli.net/2018/09/16/5b9e2a6872dea.png) 答案为绿色($3$)。 ### 第五个询问 ![](https://i.loli.net/2018/09/16/5b9e2aa71f6e3.png) 蓝色与绿色出现次数相同,但蓝色($1$)较绿色($2$)值更小,故答案为蓝色。 $1 \le n,m \le 10^5$ $1 \le color_i \le 100$ 对于其中 $50\%$ 的数据,树的结构为**一条链**。 对于另外 $50\%$ 的数据,树的结构为随机生成。 # Note: 此题卡爆栈,请谨慎 RE(大雾