Tree Coin Collecting I

题目描述

给定一棵有 n 个节点的树。有些节点包含一枚硬币。 你的任务是回答 q 个查询，形式为：从节点 a 到节点 b 的路径中，访问到一个有硬币的节点的最短路径长度是多少？

输入格式

第一行包含两个整数 n 和 q：节点数和查询数。节点编号为 1, 2, \dots, n。 第二行包含 n 个整数 c_1, c_2,\dots, c_n。如果 $c_i = 1$，节点 i 有一枚硬币。如果 $c_i = 0$，节点 i 没有硬币。你可以假设至少有一个节点有硬币。 接下来有 n-1 行描述边。每行包含两个整数 a 和 b：节点 a 和 b 之间有一条边。 最后有 q 行描述查询。每行包含两个整数 a 和 b：起点和终点。

输出格式

输出 q 个整数：对每个查询的答案。

5 4
1 0 0 1 0
2 4
2 3
1 3
3 5
1 5
3 2
4 4
5 5

2
3
0
4

提示

$1 \le n, q \le 2 \cdot 10^5$ $1 \le a, b \le n$

标签: CSES3114|高级图论问题

来源

CSES3114|高级图论问题