2563제출맞힌 사람재채점 결과채점 현황

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$)

출력

첫째 줄에 가능한 정점 후보의 개수를 출력한다.

예제 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
검수자-