60042 잔디밭의 개미굴 Diamond IV

문제

KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 $N$ 개의 방으로 구성되어 있으며, 서로 다른 두 개미굴을 직접 잇는 $N - 1$ 개의 통로가 있고, 임의의 서로 다른 두 개미굴 사이를 통로들을 통해서 항상 이동할 수 있다. 즉, 개미굴은 $N$ 개의 정점으로 구성된 트리이다. 각 방에는 $1$ 이상 $N$ 이하의 번호가 붙어 있다.

개미굴의 각 방에는 최대 한 마리의 개미가 살 수 있다. 만약에 두 개미가 사는 방이 통로로 직접 연결되어 있다면, 두 개미는 서로 불편해한다. 따라서, 현재 개미굴의 각 통로가 연결하는 두 방 중, 최대 한 방에만 개미가 살고 있다.

개미들은 똑똑하기 때문에, 이 조건을 만족하는 하에 최대한 많은 개미들이 현재 개미굴에 살고 있다. 다시 말해, 현재 개미굴에 한 마리의 개미가 새롭게 들어온다면, 개미굴의 각 방에 개미를 어떻게 배치하더라도 위 조건을 만족시킬 수 없다.

화창한 여름날, KOI 공원에는 많은 사람들이 소풍을 나오고 있다. 사람들이 잔디밭에서 소풍을 즐기다 보면, 개미굴을 이루는 흙이 으스러지면서 서로 다른 두 방을 잇는 통로가 정확히 하나 생긴다. 이때 통로가 생기는 두 방은 원래도 통로로 직접 연결된 방일 수 있다. 다시 말해, 어떠한 두 정수 $1 \le i < j \le N$ 에 대해, $i$ 번 방과 $j$ 번 방을 잇는 통로가 새롭게 생길 수 있으며, 이는 이전에 $i$ 번 방과 $j$ 번 방을 잇는 통로가 있었는지 여부와 무관하다.

이렇게 통로가 생김에 따라, 어떠한 두 개미가 사는 방이 직접 연결되면서 불편해지는 개미의 쌍이 생기게 될 수 있다. 이에 따라 현재 개미굴에 살고 있는 개미들이 배치를 바꾸어서 조건을 만족시켜야 할 수도 있다. $(i, j)$ 의 선택에 따라서 이것이 가능한 경우도 있지만, 어떤 경우에는 현재 살고 있는 개미들이 어떻게 배치를 바꾸더라도 조건을 만족시키는 것이 불가능할 수도 있다. 이러한 경우에는 살고 있던 개미들이 쫓겨나야 할 수도 있다.

만약 어떠한 두 정수 $1 \le i < j \le N$에 대해, $i$ 번 방과 $j$ 번 방을 잇는 통로가 새롭게 생길 때, 개미들이 아무도 서로를 쫓아내지 않고 적절한 재배치를 통해 조건을 만족시킬 수 있다면 이것을 평화로운 쌍 이라고 하자. 개미굴의 구조가 주어질 때, 당신은 평화로운 쌍 의 개수를 세어야 한다.

입력

첫 번째 줄에 $N$ 이 주어진다.

이후 $N-1$ 개의 줄에 각 통로가 잇는 두 방의 번호 $u$와 $v$가 주어진다.

출력

첫 번째 줄에 평화로운 쌍의 개수를 출력하라.

제한

• $2 \le N \le 250\,000$
• $u \neq v$
• $1 \leq u, v \leq N$
• 주어지는 개미굴은 트리 구조이다.

서브태스크

번호	배점	제한
1	8	$N \le 16$
2	6	$N \le 80$
3	18	$N \le 400$
4	18	$N \le 2\,000$
5	6	$N \le 10\,000$
6	8	$N \le 50\,000$
7	36	추가 제약 조건이 없음.

4
1 2
1 3
1 4

3

6
1 2
2 3
3 4
4 5
5 6

15

7
1 2
1 3
2 4
2 5
3 6
3 7

11