택배 운송

2050년, 택배 최적화 연구소(KOI, Kurier Optimization Institute)는 전국 규모의 로봇 기반 택배 운송망을 구축하였다.

전국에는 $1$부터 $N$까지의 번호가 붙은 $N$개의 물류센터가 $N-1$개의 도로로 연결되어 있다. 각 도로에는 $1$부터 $N-1$까지의 번호가 붙어 있으며, 이 중 $i$ ($1 \le i \le N-1$)번 도로는 $U_i$번 물류센터와 $V_i$번 물류센터를 두 끝점으로 하고, 길이가 $W_i$인 선분이다. 한 물류센터에서 다른 어떤 물류센터로도 하나 이상의 도로를 거쳐 도달할 수 있다. 즉, 택배 운송망은 물류센터가 도로를 통해 연결된 트리 구조이다. 또한, 서로 다른 두 도로는 양 끝점을 제외한 어떤 점에서도 만나지 않는다.

각 물류센터 및 각 도로 위의 임의의 점을 모두 하나의 지점이라고 하자. 물류센터와 도로의 구조가 트리이므로, 서로 다른 두 지점 사이에는 반드시 유일한 단순 경로가 존재한다. 두 지점 $x$, $y$ 사이의 거리 $d(x,y)$를 "지점 $x$에서 지점 $y$로 가는 단순 경로를 따라 이동할 때 거쳐야 하는 도로의 총 길이"로 정의하자. 단, $x=y$이면 $d(x,y)=0$이다.

일부 물류센터에는 전파 범위가 주어진 로봇이 배치된다. 전파 범위가 $X$인 로봇의 초기 위치가 지점 $p$라면, 이 로봇은 조건 $d(p,z)\le X$를 충족하는 모든 지점 $z$ 사이를 자유롭게 왕복하며 이동할 수 있고, 자신이 이동 가능한 범위 내의 임의의 지점에서 택배를 들어올리거나 내려놓을 수 있다.

당신은 연구소의 책임자로서, 처음에 $1$번 물류센터에 있는 택배를 $N$번 물류센터까지 운송할 수 있을지 판단하려고 한다. 로봇들은 서로 협력하여 택배를 운송할 수 있다. 즉, 한 로봇이 어느 지점에 택배를 내려놓으면 다른 로봇이 바로 그 지점에서 다시 택배를 들어올려 운송을 계속할 수 있다.

당신은 총 $Q$개의 시나리오에 대해, 로봇이 서로 협력하여 $1$번 물류센터에 있는 택배를 $N$번 물류센터까지 운송할 수 있을지 판단하여야 한다. $j$ ($1\leq j\leq Q$)번째 시나리오의 형식은 다음과 같다.

• $1$ $A_j$ $B_j$: $j$번째 시나리오는 $j-1$번째 시나리오의 상황에서, 초기 위치가 $A_j$번 물류센터이고 전파 범위가 $B_j$인 로봇 하나가 추가된 상황이다.
• $2$ $C_j$: $j$번째 시나리오는 $j-1$번째 시나리오의 상황에서, $C_j$ 번째 시나리오에서 새로 추가된 로봇을 제거한 상황이다. $C_j$ 번째 시나리오는 로봇을 새로 추가하는 시나리오임이 보장된다.

단, $0$번째 시나리오는 초기에 아무 로봇도 배치되지 않은 상황으로 간주한다.

각 시나리오에 대하여, 로봇이 서로 협력하여 $1$번 물류센터에 있는 택배를 $N$번 물류센터까지 운송할 수 있는지 판단하는 프로그램을 작성하라.

• 주어지는 모든 수는 정수이다.
• $2\leq N\leq 200\,000$
• $1\leq Q\leq 200\,000$
• $1\leq i\leq N-1$인 각 $i$에 대하여, $1\leq U_i, V_i\leq N$이고 $1\leq W_i\leq 10^9$
• 운송망은 연결되어 있다.

• $1\leq j\leq Q$인 각 $j$에 대하여:

  • $j$번째 시나리오가 로봇을 새로 추가하는 시나리오라면, $1\leq A_j\leq N$이고 $1\leq B_j\leq 10^{15}$이다.
  • $j$번째 시나리오가 로봇을 제거하는 시나리오라면, $1\leq C_j\leq j-1$이고 $C_j$ 번째 시나리오는 로봇을 새로 추가하는 시나리오이다. 같은 로봇이 2회 이상 제거되지 않는다.

1. (8점) $N\leq 100$. $Q\leq 6$. $1\leq i\leq N-1$인 각 $i$에 대하여, $W_i\leq 10$이다.
2. (13점) $1\leq i\leq N-1$인 각 $i$에 대하여, $U_i=i$이고 $V_i=i+1$이다. 또한, $N, Q\leq 2\,500$이다.
3. (25점) $N, Q\leq 2\,500$
4. (27점) $1\leq i\leq N-1$인 각 $i$에 대하여, $U_i=i$이고 $V_i=i+1$이다.
5. (30점) 모든 시나리오는 로봇을 새로 추가하는 시나리오이다.
6. (26점) $1\leq i\leq N-1$인 각 $i$에 대하여, $W_i=1$. $1\leq j\leq Q$인 각 $j$에 대하여, $j$번째 시나리오가 로봇을 새로 추가하는 시나리오라면, $B_j\leq 10$이다.
7. (21점) 추가 제약 조건 없음

첫째 줄에 두 정수 $N$, $Q$가 공백을 사이에 두고 주어진다.

다음 $N-1$개의 줄에는 도로의 정보가 주어진다. 이 중 $i$ ($1 \le i \le N-1$)번째 줄에는 세 정수 $U_i$, $V_i$, $W_i$가 공백을 사이에 두고 주어진다.

다음 $Q$개의 줄에는 시나리오의 정보가 주어진다. 이 중 $j$ ($1 \le j \le Q$)번째 줄에는 $j$번째 시나리오에 대한 정보가 지문에 제시된 형식대로 주어진다.

$Q$개의 줄을 출력한다. $j$ ($1 \le j \le Q$)번째 줄에는 $j$번째 시나리오에서 택배 운송이 가능하다면 YES를, 불가능하다면 NO를 출력한다.