31744번 - Antifreeze 서브태스크

문제

"숨이 막힐 것 같이 차가웠던 공기 속에..."

경기과학고의 본관은 $N$개의 교실을 $N-1$개의 복도가 연결한 트리 구조이다. 교실 $U_i$와 교실 $V_i$ 사이에는 거리 $W_i\ \text{m}$인 복도가 존재한다. $(1 \leq i \leq N-1)$ 원래대로라면 모든 교실의 난방 기구가 작동하는 것이 당연하지만, 경기과학고는 일부 교실만 난방 기구가 작동한다! (이거 진짜예요!!) $A_i$가 0ドル$이면 $i$번 교실의 난방 기구가 작동하지 않고, 1ドル$이면 $i$번 교실의 난방 기구가 작동한다. $(1 \leq i \leq N)$ 난방 기구가 작동하는 교실은 2개 이상 존재한다.

당신은 난방 기구가 존재하는 교실에서 시작하여 다른 난방 기구가 존재하는 교실까지 가려고 한다. 당신은 초기에 온도가 $T$이고. 당신의 온도는 1ドル$초에 1ドル$씩 감소한다. 당신의 속도는 1ドル\ \text{m/s}$이고, 이동한 거리만큼 온도가 내려간다고 생각해도 된다. 온도가 음수가 되면 당신은 얼어붙어서 사망하게 된다. 난방 기구가 있는 교실에 도달하면 온도가 다시 $T$가 된다. 온도가 정확히 0ドル$인 시점에 난방 기구가 있는 교실에 도달하는 것도 허용된다.

당신은 다음과 같은 질문에 $Q$번 답해야 한다. $i(1\leq i\leq Q)$번째 질문은 다음과 같다: 교실 $X_i$부터 교실 $Y_i$까지 얼어붙지 않고 도달할 수 있는가? 교실 $X_i$와 $Y_i$는 모두 난방 기구가 작동하는 교실 중 하나이다.

입력

첫 번째 줄에 경기과학고 본관의 교실 개수 $N$과 시작 온도 $T$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 수 $A_i (1 \leq i \leq N)$이 공백으로 구분되어 주어진다. $A_i$는 0ドル$ 또는 1ドル$이다.

이후 $N-1$개의 줄에 걸쳐 그중 $i (1 \leq i \leq N-1)$번째 줄에 복도에 대한 정보 $U_i, V_i, W_i$가 공백으로 구분되어 주어진다.

다음 줄에 답해야 하는 질문의 개수 $Q$가 주어진다.

이후 $Q$개의 줄에 걸쳐 그중 $i (1 \leq i \leq Q)$번째 줄에 $i$번째 질문에 대한 정보 $X_i, Y_i$가 공백으로 구분되어 주어진다.

출력

$Q$개의 줄을 출력한다.

$i (1 \leq i \leq Q)$번째 줄에는 $i$번째 질문의 답이 "가능하다" 이면 1ドル$을 출력하고, "불가능하다"이면 0ドル$을 출력한다.

제한

• 2ドル\leq N \leq 100,000$
• 1ドル\leq T \leq 10^9$
• $A_i \in \{ 0,1 \} \ (1\leq i \leq N),ドル 난방 기구가 작동하는 교실이 2개 이상 존재한다.
• 1ドル \leq U_i, V_i \leq N , U_i\neq V_i\ (1\leq i \leq N-1)$
• 주어지는 경기과학고 본관을 나타내는 그래프는 트리 구조이다.
• 1ドル\leq W_i \leq 10^9\ (1\leq i \leq N)$
• 어떤 두 교실 사이의 거리도 10ドル^9\ \text{m}$를 넘지 않는다.
• 1ドル\leq Q \leq 100,000$
• 1ドル \leq X_i,Y_i \leq N , X_i \neq Y_i, A_{X_i}=A_{Y_i}=1 \ (1\leq i \leq Q)$
• 문제에서 주어지는 모든 수는 정수이다.

서브태스크

노트