슥삭슥삭 나무자르기

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

요약
트리에서 각 질의마다 a에서 b로 가는 경로의 모든 간선을 지운 뒤 c와 d가 여전히 연결되는지 판정한다.
난이도

어려움10점 중 8점

유형
트리, 누적 합, 연결 리스트
정답자
아직 제출이 없습니다

문제

11부터 NN까지의 번호가 붙은 NN개의 정점과 N−1N-1개의 간선으로 이루어진 트리가 주어진다. 이제 당신은 이 트리에 대해 다음 질문을 QQ번 답해야 한다.

  • aa bb cc dd: 정점 aa에서 bb로 가는 최단 경로에 속한 모든 간선을 제거하였을 때, cc에서 dd로 가는 경로가 존재한다면 “YES”를 존재하지 않는다면 “NO”를 출력한다. 따옴표는 출력하지 않는다.

질문의 결과는 다른 질문에 영향을 끼치지 않는다. 또한 트리의 루트는 항상 11번 정점이며 모든 간선은 양방향이다.

입력

입력의 첫 번째 줄에 NN과 QQ가 공백으로 구분되어 주어진다. (2≤N≤100,0002\le N \le 100\\,000; 1≤Q≤300,0001 \le Q \le 300\\,000)

두 번째 줄부터 N−1N-1개 줄 각각에는 트리의 간선이 연결하는 22개의 정점의 번호와 uu와 vv가 공백으로 구분되어 주어진다. 이는 정점 uu와 정점 vv를 연결하는 양방향 간선이 존재한다는 의미이다. (1≤u,v≤N1 \le u, v \le N; u≠vu \ne v)

N+1N+1번째 줄부터 QQ개의 줄에 걸쳐 질문을 나타내는 44개의 정수 aa, bb, cc, dd가 공백으로 구분되어 주어진다. (1≤a,b,c,d≤N1 \le a, b, c, d \le N)

출력

QQ개의 줄에 걸쳐 질문의 답을 한 줄에 하나씩 출력한다.

예제3

  1. 예제 1

    입력
    8 4
1 2
1 3
3 4
3 5
3 6
4 7
4 8
6 7 2 3
6 7 7 8
4 6 1 5
4 7 4 8
    예상 출력
    YES
NO
YES
YES

  2. 예제 2

    입력
    2 2
1 2
1 1 2 2
1 2 1 2
    예상 출력
    YES
NO

  3. 예제 3

    입력
    19 6
1 2
1 3
1 4
1 5
4 6
4 7
5 8
5 9
6 10
6 11
6 12
9 13
9 14
9 15
14 16
15 17
16 18
16 19
2 3 5 6
5 11 8 15
7 11 12 10
9 14 16 19
9 16 14 19
12 17 14 11
    예상 출력
    YES
YES
YES
YES
NO
NO