경로 위의 교차로
골드 I의견: 0
\(N\)개의 교차로가 도로로 연결되어 트리를 이룬다.
\(Q\)개의 질의가 주어지며, 각 질의는 세 교차로 \(a, b, c\)로 이루어진다. \(a\)에서 \(b\)로 가는 (유일한) 최단 경로 위에 교차로 \(c\)가 포함되어 있으면 YES, 아니면 NO를 출력하라. 경로의 양 끝점 \(a, b\)도 경로에 포함된다.
\(1 \le N \le 100{,}000\), \(1 \le Q \le 100{,}000\), \(1 \le u,v,a,b,c \le N\). 입력 그래프는 항상 트리이다.
첫째 줄에 \(N\). 다음 \(N-1\)개의 줄에 도로 \(u\;v\). 그 다음 줄에 \(Q\). 이후 \(Q\)개의 줄에 \(a\;b\;c\)가 주어진다. 교차로는 \(1\)번부터 번호가 매겨진다.
각 질의마다 YES 또는 NO를 한 줄에 출력한다.
5
1 2
1 3
3 4
3 5
3
2 4 1
2 4 5
4 5 3
YES
NO
YES\(2\to4\) 경로는 \(2,1,3,4\). \(1\)은 경로 위에 있어 YES, \(5\)는 없어 NO. \(4\to5\) 경로는 \(4,3,5\)이고 \(3\)이 있어 YES.
4
1 2
2 3
3 4
2
1 4 3
1 4 1
YES
YES\(1\to4\) 경로는 \(1,2,3,4\). \(3\)은 경로 위라 YES, \(1\)도 끝점이므로 경로 위라 YES.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
경로 위의 교차로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
경로 위의 교차로