← 返回题目列表

AtCoder · arc048_d

D. 章鱼烧店和Q人高桥君

中文机器翻译题面 查看原题

問題文

AtCoder 城市有 编号至 1 到 N 有 N 个城镇,分别是 N-1 一本书可以在两个方向上通过的距离 它们由 1 道路连接。 您可以通过多条道路从任何城镇前往任何其他城镇。

Takahashi先生在AtCoder City。 Q 有人,i 高桥君是镇 s_i 卡拉町 我想去 t_i 。

AtCoder市的几个城镇都有章鱼烧店。高桥和大家,2 每秒距离 1 我走路的速度与走路时的速度相同,但是在有章鱼烧店的小镇吃完章鱼烧后,我的步行速度变慢了。 1 每秒距离 1 这是您前进的速度。 而且,高桥和他的朋友们都是清淡饮食者,所以他们吃章鱼烧的次数不会超过一次。当然,路过有章鱼烧店的小镇,不吃章鱼烧也是可以的。 另外,不吃章鱼烧就不要进城。 您可能会到达 t_i 。

考虑到AtCoder城市和城镇的连接关系, Q 高桥君,你为每个人都表现得最好的小镇。 求前往 s_i 卡拉町 我想去 t_i所需的最短时间。 由于高桥和他的朋友都是章鱼烧专业人士,所以我们可以忽略吃章鱼烧所需的时间。


入力

输入是按以下格式从标准输入给出的。

N Q
A_1 B_1
.
.
.
A_{N-1} B_{N-1}
S
s_1 t_1
.
.
.
s_Q t_Q
  • 1 行包含一个整数 N(1 ≦ N ≦ 100000) 和 Q(1 ≦ Q ≦ 100000) 作为空格分隔符给出。
  • 继续 N-1 行包含 代表第 i 条路径信息的整数 A_i, B_i(1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i ≠ B_i) 作为空格分隔符给出。这就是小镇 A_i 和镇 表示有一条路径连接 B_i 。
  • 以下行包含 仅由0 和 1 组成的长度 给出了字符串 N 。这个 i 第一个字母是 0 能时镇 i 没有章鱼烧餐厅。1 能时镇 i 表示有一家章鱼烧餐厅。
  • 继续 Q 行包含 代表第i 一个整数,表示人的运动起点和终点,Takahashi。 s_i,t_i(1 ≦ s_i ≦ N, 1 ≦ t_i ≦ N) 。

出力

输出是 由 Q 行组成。

i 行中, 一个整数,表示第i 让我们计算一下这个人的高桥君达到最佳移动所需的最短时间。 1 行输出。

不要忘记输出末尾的换行符。


入力例1

7 4
1 2
2 3
2 4
4 5
5 6
6 7
0010000
1 5
1 7
6 1
3 3

出力例1

6
9
8
0

在第一个查询中,镇 最好按顺序访问 1,2,4,5 。 在第 2 次查询中,镇 1,2,3,2,4,5,6,7 和沿途的城镇。 最好去 3 的章鱼烧店。


入力例2

5 2
3 2
2 4
1 4
2 5
00000
1 5
2 3

出力例2

6
2

入力例3

12 10
1 2
2 3
2 4
10 12
1 5
3 11
5 6
9 10
5 7
3 9
8 7
000100100010
1 2
1 4
8 3
6 12
12 8
8 12
6 8
8 6
1 12
5 12

出力例3

2
4
6
11
14
9
5
4
9
9