34769번 - 트리 게임

문제

트리에서 두 플레이어 $A$와 $B$가 아래의 규칙대로 게임을 하려고 한다.

$A$는 정점 $i$에 있고, $B$는 정점 $j$에 있다. $A$와 $B$는 차례대로 아래의 행동을 반복한다.

• $A$는 현재 위치로부터 거리가 1ドル$인 정점 중 하나로 움직인다.
• $B$는 현재 위치로부터 거리가 2ドル$인 정점 중 하나로 움직인다.

플레이어는 각자 자신의 차례에 가만히 있을 수 없으며, 반드시 움직여야 한다.

상대방이 있는 위치로 움직였다면, 상대방을 잡게 되어 움직인 플레이어가 게임에서 승리한다. 만약 $B$가 10ドル^{100}$번 움직일 때까지도 승부가 나지 않는다면, 무승부가 된다.

두 플레이어는 매우 똑똑하므로 항상 최선으로 행동한다.

모든 시작 위치 쌍 $(i, j)$ $(1\leq i, j\leq N; i ≠ j)$ 에서 게임을 진행할 때, 플레이어 $A$가 이기는 횟수를 구해보자.

입력

트리의 정점의 개수를 의미하는 정수 $N$이 주어진다. $(4\leq N\leq 200,円 000)$

이어지는 $N-1$개의 줄에, 간선으로 연결된 두 정점을 의미하는 정수 $u, v$가 공백으로 구분되어 주어진다. $(1\leq u, v\leq N)$

두 플레이어가 어떤 위치에 있더라도 규칙에 따라 이동할 수 있는 트리임이 보장된다. 즉, 트리의 지름이 3ドル$ 이상임이 보장된다.

출력

모든 서로 다른 시작 위치에서 게임을 진행할 때, 플레이어 $A$가 이기는 횟수를 출력한다.

제한

노트

트리는 사이클이 없는 연결 그래프입니다. 즉, $N$개의 정점으로 이루어진 트리는 $N-1$개의 간선으로 사이클 없이 모든 정점이 연결되어 있습니다.

트리에서 두 정점 $u, v$사이의 거리란, $u$에서 $v$로 가는 경로에 포함된 간선의 개수를 의미합니다.