6291：对称数

题目描述

小Q认为，偶数具有对称美，而奇数则没有。

给定一棵$n$个点的树，任意两点之间有且仅有一条直接或间接路径。这些点编号依次为$1$到$n$，其中编号为$i$的点上有一个正整数$a_i$。

定义集合$S(u,v)$为$u$点到$v$点的唯一最短路径上经过的所有点$x$(包括$u$和$v$)对应的正整数$a_x$的集合。小Q将在$m$个$S(u,v)$中寻找最小的对称数。因为偶数具有对称美，所以对称数是指那些出现了偶数次(包括$0$次)的正整数。

请写一个程序，帮助小Q找到最小的对称数。

输入解释

第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。

每组数据第一行包含两个正整数$n,m(1\leq n,m\leq 200000)$，分别表示点数和询问数。

第二行包含$n$个正整数$a_1,a_2,...,a_n(1\leq a_i\leq 200000)$，依次表示每个点上的数字。

接下来$n-1$行，每行两个正整数$u_i,v_i(1\leq u_i,v_i\leq n,u_i\neq v_i)$，表示一条连接$u_i$和$v_i$的双向树边。

接下来$m$行，每行两个正整数$u_i,v_i(1\leq u_i,v_i\leq n)$，依次表示每个询问。

输出解释

对于每个询问输出一行一个正整数，即最小的对称数。

输入样例

输出样例

2
1
1

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 "字节跳动杯"2018中国大学生程序设计竞赛-女生专场

源链接： HDU-6291

最后修改于 2020-10-25T23:30:01+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
30000/15000MS(Java/Others)	512000/512000K(Java/Others)