D - たこ焼き屋とQ人の高橋君 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

AtCoder市には 1 から N までの番号のついた N 個の町があり、それらは N-1 本の双方向に通行可能な距離 1 の道路によって結ばれています。 どの町からどの町へも、いくつかの道を経由してたどり着くことが出来ます。

AtCoder市には高橋君が 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 人目の高橋君の移動の始点と目的地を表す整数 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