2563번 - 트리의 루트를 찾아라
시간 제한1 초
메모리 제한1024 MB
제출0
정답0
맞힌 사람0
정답 비율0.00%
문제
형진이는 트리의 루트를 까먹었다. 유일하게 기억하는 것은 $LCA(a, b) = x$라는 것뿐이다.
트리의 루트로 가능한 정점 후보의 개수를 구해보자.
트리의 루트로 가능한 정점 후보의 개수를 구해보자.
입력
첫째 줄에 정점의 개수 $N$이 주어진다. ($1 \le N \le 200,000$)
그 다음 $N-1$개의 줄에 걸쳐 간선의 정보 $a_i$, $b_i$가 주어진다. 이는 $a_i$번 정점과 $b_i$번 정점이 연결되어 있다는 뜻이다. ($1 \le a_i, b_i \le N$)
다음으로 $a, b, x$가 주어진다. 이는 이 트리의 $LCA(a, b) = x$라는 의미이다. ($1 \le a, b, x \le N$)
그 다음 $N-1$개의 줄에 걸쳐 간선의 정보 $a_i$, $b_i$가 주어진다. 이는 $a_i$번 정점과 $b_i$번 정점이 연결되어 있다는 뜻이다. ($1 \le a_i, b_i \le N$)
다음으로 $a, b, x$가 주어진다. 이는 이 트리의 $LCA(a, b) = x$라는 의미이다. ($1 \le a, b, x \le N$)
출력
첫째 줄에 가능한 정점 후보의 개수를 출력한다.
예제 1
예제 입력 1
7 1 2 2 3 2 4 4 5 5 6 6 7 3 4 4
예제 출력 1
4
예제 2
예제 입력 2
7 1 2 2 3 2 4 4 5 5 6 6 7 3 4 2
예제 출력 2
2
문제 정보
| 출처 | school > 연세대학교 > 연세대학교 프로그래밍 경진대회 2024 |
|---|---|
| 출제자 | plast7 |
| 검수자 | - |