{"problem":{"name":"[蓝桥杯 2024 省 A] 零食采购","description":{"content":"小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 $n$ 颗星球，由 $n-1$ 条航路连接为连通图，第 $i$ 颗星球卖第 $c_i$ 种零食特产。小蓝想出了 $q$ 个采购方案，第 $i$ 个方案的起点为星球 $s_i$ ，终点为星球 $t_i$ ，对于每种采购方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的零食（包括起点终点），请计算每种采购方案最多能买多少种不","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10391"},"statements":[{"statement_type":"Markdown","content":"小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 $n$ 颗星球，由 $n-1$ 条航路连接为连通图，第 $i$ 颗星球卖第 $c_i$ 种零食特产。小蓝想出了 $q$ 个采购方案，第 $i$ 个方案的起点为星球 $s_i$ ，终点为星球 $t_i$ ，对于每种采购方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的零食（包括起点终点），请计算每种采购方案最多能买多少种不同的零食。\n\n## Input\n\n输入的第一行包含两个正整数 $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 $，用一个空格分隔，表示一个采购方案。\n\n## Output\n\n输出 $q$ 行，每行包含一个整数，依次表示每个采购方案的答案。\n\n[samples]\n\n## Note\n\n第一个方案路线为 $\\{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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10391","tags":["2024","最近公共祖先 LCA","蓝桥杯省赛","状压 DP"],"sample_group":[["4 2\n1 2 3 1\n1 2\n1 3\n2 4\n4 3\n1 4","3\n2"]],"created_at":"2026-03-03 11:09:25"}}