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\) 번 방을 잇는 통로가 새롭게 생길 때, 개미들이 아무도 서로를 쫓아내지 않고 적절한 재배치를 통해 조건을 만족시킬 수 있다면 이것을 평화로운 쌍 이라고 하자. 개미굴의 구조가 주어질 때, 당신은 평화로운 쌍 의 개수를 세어야 한다.

• \(2 \le N \le 250\,000\)
• \(u \ne v\)이고, \(1 \le u, v \le N\)
• 주어지는 개미굴은 트리 구조이다.

첫 번째 줄에 \(N\) 이 주어진다.

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

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2023 > 2차 대회 > 고등부 3번