Tree Coin Collecting II

题目描述

给定一棵有 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

6
5
6
8

提示

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

标签: CSES3149|高级图论问题

来源

CSES3149|高级图论问题