다리 검사

시간 제한4초메모리 제한256 MB

요약

가중치가 있는 트리와 각자 경로를 걷는 두 테스터가 주어질 때, 각 질의마다 두 사람이 같은 다리 위에 양의 길이 구간 동안 동시에 있는지 판정한다.

난이도: 어려움10점 중 8점
유형: 트리, 동적 계획법, 누적 합, 수학
정답자: 아직 제출이 없습니다

문제

작은 섬나라가 교통망을 놓고 있다. 섬 일부는 다리로 이어져 있고, 어느 두 섬 사이에도 다리를 따라가는 경로가 정확히 하나뿐이다. 즉 다리는 트리를 이룬다. 다리의 길이는 서로 다를 수 있다.

다리를 개통하기 전에 안전을 검사해야 한다. 앞으로 $q$ 일 동안 매일 검사원 두 명이 각자 맡은 경로를 속도 $1$ 로 걷는다. $j$ 번째 검사원은 시각 $s_j$ 에 섬 $b_j$ 를 출발해 섬 $b_j$ 와 섬 $e_j$ 를 잇는 유일한 경로를 걸어 섬 $e_j$ 에서 멈춘다. 두 검사원의 출발 시각은 서로 다를 수 있다.

어떤 다리 하나를 두 검사원이 동시에 걷고 있던 시간이 길이가 $0$ 보다 큰 구간이면, 그날 그 다리는 검사되었다고 한다. 두 검사원이 섬에서 한 순간만 마주치는 경우는 검사로 치지 않는다. 하루하루는 서로 독립이다.

$q$ 일 각각에 대해 그날 검사된 다리가 하나라도 있는지 판정하라.

입력

첫째 줄에 섬의 수 $n$ 과 검사 일수 $q$ 가 주어진다. ( $2 \le n \le 10^5$ , $1 \le q \le 10^5$ )

다음 $n-1$ 개 줄에는 다리 정보가 정수 세 개 $u_i$ , $v_i$ , $l_i$ 로 주어진다. ( $1 \le u_i, v_i \le n$ , $1 \le l_i \le 10^9$ ) $i$ 번째 다리는 섬 $u_i$ 와 섬 $v_i$ 를 길이 $l_i$ 로 잇는다.

다음 $q$ 개 줄에는 하루치 검사 계획이 정수 여섯 개 $b_1$ $e_1$ $s_1$ $b_2$ $e_2$ $s_2$ 로 주어진다. ( $1 \le b_j, e_j \le n$ , $b_j \ne e_j$ , $1 \le s_j \le 10^9$ ) 앞의 세 수가 첫 번째 검사원의 출발 섬, 도착 섬, 출발 시각이고 뒤의 세 수가 두 번째 검사원의 것이다.

출력

$q$ 개 줄을 출력한다. $i$ 번째 줄에는 $i$ 일차에 검사된 다리가 하나라도 있으면 YES를, 없으면 NO를 출력한다.

예제2

예제 1

입력

8 6
1 2 3
1 3 1
1 4 2
2 5 5
2 6 1
5 7 2
5 8 4
5 3 2 7 4 2
8 6 1 1 7 6
4 5 1 4 5 10
7 8 3 3 4 5
6 7 6 5 1 2
2 1 10 8 3 3

예상 출력

YES
YES
NO
NO
NO
YES

예제 2

입력

2 6
1 2 4
1 2 1 1 2 1
1 2 1 1 2 5
1 2 1 1 2 4
1 2 1 2 1 1
1 2 1 2 1 9
1 2 5 2 1 1

예상 출력

YES
NO
YES
YES
NO
NO