链接: https://cses.fi/problemset/task/3114

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一棵含有 $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$ 个整数：各查询的答案。

数据范围

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

样例输入

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