{"raw_statement":[{"iden":"statement","content":"小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 $n$ 颗星球，由 $n-1$ 条航路连接为连通图，第 $i$ 颗星球卖第 $c_i$ 种零食特产。小蓝想出了 $q$ 个采购方案，第 $i$ 个方案的起点为星球 $s_i$ ，终点为星球 $t_i$ ，对于每种采购方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的零食（包括起点终点），请计算每种采购方案最多能买多少种不同的零食。"},{"iden":"input","content":"输入的第一行包含两个正整数 $n$，$q$，用一个空格分隔。  \n第二行包含 $n$ 个整数 $c_1,c_2,\\cdots, c_n$，相邻整数之间使用一个空格分隔。  \n接下来 $n - 1$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，用一个空格分隔，表示一条\n航路将星球 $u_i$ 与 $v_i$ 相连。  \n接下来 $q$ 行，第 $i$ 行包含两个整数 $s_i\n, t_i $，用一个空格分隔，表示一个采购方案。"},{"iden":"output","content":"输出 $q$ 行，每行包含一个整数，依次表示每个采购方案的答案。"},{"iden":"note","content":"第一个方案路线为 $\\{4, 2, 1, 3\\}$，可以买到第 $1, 2, 3$ 种零食；  \n第二个方案路线为 $\\{1, 2, 4\\}$，可以买到第 $1, 2$ 种零食。\n\n对于 20% 的评测用例，$1 ≤ n, q ≤ 5000 $；    \n对于所有评测用例，$1 ≤ n, q ≤ 10^5，1 ≤ c_i ≤ 20，1 ≤ u_i\n, v_i ≤ n，1 ≤ s_i\n, t_i ≤ n$。"}],"translated_statement":null,"sample_group":[["4 2\n1 2 3 1\n1 2\n1 3\n2 4\n4 3\n1 4","3\n2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}