L - 消防署と緊急出動 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

ある地域には 1 から N までの番号が付いた N 個の町があり、N - 1 本の双方向の道路で結ばれています。任意の 2 つの町の間の経路は一意に定まります（すなわち、町と道路は木構造をなします）。道路 i（1 \leq i \leq N-1）は町 A_i と町 B_i を結び、通過に C_i 分かかります。

2 つの町の間の所要時間を、それらを結ぶ一意な経路上の道路の通過時間の合計と定めます。特に、同じ町どうしの所要時間は 0 です。

N 個の町にはそれぞれ消防署があります。初期状態では、町 1 の消防署のみが開設されており、それ以外の町の消防署はすべて閉鎖されています。町 1 の消防署は常に開設されており、閉鎖されることはありません。なお、消防署が閉鎖されている町であっても、その町を経由して道路を通過することは可能です。

これから Q 個のイベントが順に発生します。イベントには次の 2 種類があります。

  • 1 X：町 X の消防署の状態を切り替える。閉鎖中であれば開設し、開設中であれば閉鎖する。
  • 2 V T：町 V で火災が発生した。現在開設されている各消防署から町 V への所要時間をそれぞれ求め、その最小値が T 分以下なら YES、そうでなければ NO を出力せよ。

タイプ 2 のイベントは問い合わせのみであり、消防署の状態を変更しません。

制約

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • 1 \leq C_i \leq 10^9
  • 与えられるグラフは木である（連結で N - 1 本の道路を持つ）
  • タイプ 1 のイベントにおいて、2 \leq X \leq N
  • タイプ 2 のイベントにおいて、1 \leq V \leq N、0 \leq T \leq 5 \times 10^{13}
  • タイプ 2 のイベントは 1 つ以上存在する
  • 入力はすべて整数である

入力

N Q
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_{N-1} B_{N-1} C_{N-1}
S_1
S_2
\vdots
S_Q

1 行目には、町の数 N とイベントの数 Q がスペース区切りで与えられる。

続く N - 1 行には、道路の情報が与えられる。i 行目（1 \leq i \leq N-1）には、道路 i が結ぶ 2 つの町の番号 A_i, B_i と通過時間 C_i（分）がスペース区切りで与えられる。

続く Q 行には、イベントの情報 S_j（1 \leq j \leq Q）が与えられる。各イベントは次のいずれかの形式である。

1 X

2 V T

出力

タイプ 2 の各イベントについて、発生した順に 1 行ずつ YES または NO を出力せよ。

入力例 1

5 8
1 2 3
1 3 5
2 4 4
2 5 2
2 4 6
1 5
2 4 3
1 4
2 4 0
1 5
2 5 2
2 3 5

出力例 1

NO
NO
YES
NO
YES

入力例 2

4 7
1 2 10
2 3 10
3 4 10
2 4 25
1 3
2 4 10
1 3
2 2 0
1 2
2 4 15

出力例 2

NO
YES
NO
NO

入力例 3

12 20
1 2 7
1 3 4
2 4 6
2 5 3
3 6 8
3 7 2
5 8 5
5 9 9
6 10 1
7 11 10
7 12 4
2 9 18
1 8
2 9 14
1 11
2 12 8
1 12
2 12 0
1 8
2 4 16
1 6
2 10 1
1 6
2 10 12
1 11
2 7 6
1 5
2 9 9
1 12
2 9 8
2 1 0

出力例 3

NO
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES

入力例 4

25 39
1 2 100
1 3 200
2 4 50
2 5 70
3 6 30
3 7 90
4 8 20
4 9 60
5 10 40
5 11 80
6 12 10
6 13 110
7 14 25
7 15 35
8 16 45
9 17 55
10 18 65
11 19 75
12 20 85
13 21 95
14 22 105
15 23 115
16 24 125
17 25 135
2 25 800
2 23 300
1 23
2 23 0
1 18
2 25 250
1 25
2 25 0
1 23
2 14 150
1 14
2 14 0
1 14
1 6
2 20 90
1 20
2 20 0
1 6
2 12 15
1 12
2 12 0
1 18
2 10 150
1 10
2 10 0
1 25
2 24 300
1 24
2 24 0
1 20
2 21 200
1 21
2 21 0
1 12
2 13 120
1 10
2 5 200
1 24
2 16 300

出力例 4

YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES

入力例 5

1 5
2 1 0
2 1 1
2 1 50000000000000
2 1 999999999
2 1 12345

出力例 5

YES
YES
YES
YES
YES

Score : 500 pts

Problem Statement

A region contains N towns numbered from 1 to N, connected by N - 1 bidirectional roads. The path between any two towns is unique (that is, the towns and roads form a tree structure). Road i (1 \leq i \leq N-1) connects town A_i and town B_i, and takes C_i minutes to traverse.

The travel time between two towns is defined as the sum of the traversal times of the roads on the unique path connecting them. In particular, the travel time between the same town is 0.

Each of the N towns has a fire station. Initially, only the fire station in town 1 is open, and the fire stations in all other towns are closed. The fire station in town 1 is always open and will never be closed. Note that even if a town's fire station is closed, it is still possible to pass through that town via roads.

Q events occur sequentially. There are two types of events:

  • 1 X: Toggle the state of the fire station in town X. If it is closed, open it; if it is open, close it.
  • 2 V T: A fire has broken out in town V. For each currently open fire station, determine the travel time to town V, and output YES if the minimum of these values is at most T minutes, otherwise output NO.

Type 2 events are queries only and do not change the state of any fire station.

Constraints

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • 1 \leq C_i \leq 10^9
  • The given graph is a tree (connected with N - 1 roads)
  • For type 1 events, 2 \leq X \leq N
  • For type 2 events, 1 \leq V \leq N, 0 \leq T \leq 5 \times 10^{13}
  • There is at least one type 2 event
  • All input values are integers

Input

N Q
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_{N-1} B_{N-1} C_{N-1}
S_1
S_2
\vdots
S_Q

The first line contains the number of towns N and the number of events Q, separated by a space.

The following N - 1 lines contain information about the roads. The i-th line (1 \leq i \leq N-1) contains the numbers of the two towns A_i, B_i connected by road i and the traversal time C_i (in minutes), separated by spaces.

The following Q lines contain the event information S_j (1 \leq j \leq Q). Each event is in one of the following formats:

1 X

2 V T

Output

For each type 2 event, output YES or NO on a separate line, in the order the events occur.

Sample Input 1

5 8
1 2 3
1 3 5
2 4 4
2 5 2
2 4 6
1 5
2 4 3
1 4
2 4 0
1 5
2 5 2
2 3 5

Sample Output 1

NO
NO
YES
NO
YES

Sample Input 2

4 7
1 2 10
2 3 10
3 4 10
2 4 25
1 3
2 4 10
1 3
2 2 0
1 2
2 4 15

Sample Output 2

NO
YES
NO
NO

Sample Input 3

12 20
1 2 7
1 3 4
2 4 6
2 5 3
3 6 8
3 7 2
5 8 5
5 9 9
6 10 1
7 11 10
7 12 4
2 9 18
1 8
2 9 14
1 11
2 12 8
1 12
2 12 0
1 8
2 4 16
1 6
2 10 1
1 6
2 10 12
1 11
2 7 6
1 5
2 9 9
1 12
2 9 8
2 1 0

Sample Output 3

NO
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES

Sample Input 4

25 39
1 2 100
1 3 200
2 4 50
2 5 70
3 6 30
3 7 90
4 8 20
4 9 60
5 10 40
5 11 80
6 12 10
6 13 110
7 14 25
7 15 35
8 16 45
9 17 55
10 18 65
11 19 75
12 20 85
13 21 95
14 22 105
15 23 115
16 24 125
17 25 135
2 25 800
2 23 300
1 23
2 23 0
1 18
2 25 250
1 25
2 25 0
1 23
2 14 150
1 14
2 14 0
1 14
1 6
2 20 90
1 20
2 20 0
1 6
2 12 15
1 12
2 12 0
1 18
2 10 150
1 10
2 10 0
1 25
2 24 300
1 24
2 24 0
1 20
2 21 200
1 21
2 21 0
1 12
2 13 120
1 10
2 5 200
1 24
2 16 300

Sample Output 4

YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES

Sample Input 5

1 5
2 1 0
2 1 1
2 1 50000000000000
2 1 999999999
2 1 12345

Sample Output 5

YES
YES
YES
YES
YES