AT_arc048_d.[ARC048D] たこ焼き屋とQ人の高橋君

AtCoder 市有 $1$ 到 $N$ 编号的 $N$ 个城镇，这些城镇通过 $N-1$ 条双向、距离为 $1$ 的道路相连。任意两个城镇之间都可以通过若干道路到达。

AtCoder 市里有 $Q$ 个高桥君，第 $i$ 个高桥君想从城镇 $s_i$ 前往城镇 $t_i$。

AtCoder 市的部分城镇设有章鱼烧店。所有高桥君初始以每 $2$ 秒走 $1$ 距离的速度行走，但如果在某个有章鱼烧店的城镇吃了章鱼烧，之后的行走速度会变为每 $1$ 秒走 $1$ 距离。每位高桥君只能吃一次章鱼烧，且可以选择经过有章鱼烧店的城镇时不吃章鱼烧，也可以不吃章鱼烧直接到达 $t_i$。

给定 AtCoder 市的城镇连接关系，请你求出对于每个高桥君，从 $s_i$ 到 $t_i$ 最优行动下所需的最短时间。吃章鱼烧所需时间可忽略不计。

输入通过标准输入给出，格式如下：

$N$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$S$
$s_1$ $t_1$
$s_2$ $t_2$
$\vdots$
$s_Q$ $t_Q$

• 第 $1$ 行包含两个整数 $N\ (1 \leq N \leq 100000)$ 和 $Q\ (1 \leq Q \leq 100000)$，以空格分隔。
• 接下来 $N-1$ 行，每行包含两个整数 $A_i, B_i\ (1 \leq A_i \leq N, 1 \leq B_i \leq N, A_i \neq B_i)$，表示城镇 $A_i$ 和城镇 $B_i$ 之间有一条道路。
• 接下来一行是长度为 $N$ 的仅由 $0$ 和 $1$ 组成的字符串 $S$。第 $i$ 个字符为 $0$ 表示城镇 $i$ 没有章鱼烧店，为 $1$ 表示有章鱼烧店。
• 接下来 $Q$ 行，每行包含两个整数 $s_i, t_i\ (1 \leq s_i \leq N, 1 \leq t_i \leq N)$，表示第 $i$ 个高桥君的起点和终点。

输出 $Q$ 行。

第 $i$ 行输出第 $i$ 个高桥君最优行动下从 $s_i$ 到 $t_i$ 所需的最短时间。

输出末尾请不要忘记换行。

样例解释 1

对于第一个询问，依次经过城镇 $1,2,4,5$ 是最优方案。对于第二个询问，依次经过城镇 $1,2,3,2,4,5,6,7$，并在途中经过城镇 $3$ 的章鱼烧店时吃章鱼烧，是最优方案。

由 ChatGPT 4.1 翻译