32656번 - 트리의 루트를 찾아라

문제

$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$번 정점의 가장 가까운 공통 조상을 의미한다.