트리의 루트를 찾아라

면접 대비

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

요약

간선으로 이어진 트리에서 루트를 모를 때 LCA(a, b)가 x가 되는 루트 후보의 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 트리, DFS
정답자: 아직 제출이 없습니다

문제

$N$ 개의 정점으로 이루어진 트리가 있다.

형진이는 이 트리의 루트를 잊어버렸다. 기억하는 것은 $LCA(a, b) = x$ 라는 것뿐이다.

트리의 루트가 될 수 있는 정점 후보의 개수를 구해보자.

입력

첫 번째 줄에 트리의 정점 개수 $N$ 이 주어진다. ( $1 \le N \le 200\,000$ )

다음 $N - 1$ 개의 줄에는 간선 정보 $u_i$ , $v_i$ 가 주어진다. 이는 $u_i$ 번 정점과 $v_i$ 번 정점이 간선으로 연결되어 있다는 뜻이다. ( $1 \le u_i, v_i \le N$ )

다음 줄에는 $a$ , $b$ , $x$ 가 주어진다. 이는 주어진 트리에서 $LCA(a, b) = x$ 라는 뜻이다. ( $1 \le a, b, x \le N$ )

입력으로는 트리의 루트가 될 수 있는 정점 후보가 적어도 하나 있는 $a$ , $b$ , $x$ 쌍만 주어진다.

출력

첫 번째 줄에 트리의 루트가 될 수 있는 정점 후보의 개수를 출력한다.

힌트

LCA(Least Common Ancestor)는 두 노드의 가장 가까운 공통 조상을 뜻한다. 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은 노드, 즉 두 노드에 가장 가까운 노드이다. 이 문제에서 $LCA(a, b)$ 는 $a$ 번 정점과 $b$ 번 정점의 가장 가까운 공통 조상을 뜻한다.

예제3

예제 1
입력
```
7
1 2
2 3
2 4
4 5
5 6
6 7
3 4 4
```
예상 출력
```
4
```
예제 2
입력
```
7
1 2
2 3
2 4
4 5
5 6
6 7
3 4 2
```
예상 출력
```
2
```
예제 3
입력
```
7
1 2
2 3
2 4
4 5
5 6
6 7
3 3 3
```
예상 출력
```
7
```