트리의 루트를 찾아라

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

요약

루트 없는 트리와 LCA(a, b) = x라는 조건 하나가 주어질 때, 루트가 될 수 있는 정점의 개수를 센다.

난이도: 보통10점 중 7점
유형: 트리, 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
```