| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 210 | 104 | 82 | 51.250% |
$N$개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 $1$번부터 $N$번까지 번호가 매겨져있다.
두 정수 $A, B$가 주어진다. $K$번 정점$(1 \le K \le N)$을 루트로 설정했을 때, $A$번 정점과 $B$번 정점의 가장 가까운 공통 조상이 $A$번 정점도 아니고 $B$번 정점도 아니게 되는 $K$의 개수를 구하여라.
첫 번째 줄에 정점의 개수 $N$과 두 정수 $A, B$가 주어진다. $(4 \le N \le 300,000$; $1 \le A, B \le N$; $A \neq B)$
두 번째 줄부터 $N-1$개의 줄에 걸쳐 각 간선이 연결하는 두 정점 $u, v$가 공백으로 구분되어 주어진다. ($1 \le u, v \le N$)
주어지는 입력은 트리임이 보장된다.
문제의 조건을 만족하는 $K$의 개수를 출력한다.
4 1 4 1 2 2 3 3 4
2
6 2 4 1 2 2 3 1 4 4 5 4 6
1
해당 예제의 트리에서, 트리의 루트를 $5$번 정점으로 설정하면, $A$번 정점과 $B$번 정점의 가장 가까운 공통 조상은 $B$번 정점이 되어 문제의 조건을 만족하지 않는다.
그러나 트리의 루트를 $1$번 정점으로 설정하면, $A$번 정점과 $B$번 정점의 가장 가까운 공통 조상은 $1$번 정점이 되어 문제의 조건을 만족하게 된다.
가장 가까운 공통 조상에 관한 설명은 링크를 참고 하면 된다.