문제
루트가 있는 트리에서 트리의 깊이를 다음과 같이 정의하자.
1. 루트의 깊이는 0이다.
2. 부모의 깊이가 d라면 그 자식의 깊이는 d + 1이다.
S(T, d) 를 트리 T에서 깊이가 d인 노드의 개수라고 하자. 이때, 두 개의 루트가 있는 트리 Ta과 Tb에서 모든 음이 아닌 정수 d에 대하여
S(Ta, d)와 S(Tb, d)가 같다면 두 트리 Ta과 Tb는 유사도가 같다고 정의한다.
노드의 개수가 N개인 루트가 있는 트리 T가 주어진다. 트리 T의 노드는 1에서 N까지 번호가 매겨져 있으며 루트는 1번이다.
Tk를 노드 k를 루트로 하는 부분트리라고 할 때, i<j인 모든 순서쌍(i, j)에 대하여 Ti와 Tj의 유사도가 같은 쌍의 개수를 구하는 것이 여러분에게 주어진 과제이다.
입력
첫 행에 노드의 개수 N( 1 ≤ N ≤ 100,000)이 주어진다.
다음 N-1개의 행에 걸쳐 ai 와 bi순서쌍이 공백을 구분하여 주어지는데 이는 bi의 부모가 ai임을 나타낸다.
( 1 ≤ ai, bi ≤ N 이고 ai ≠ bi)
주어지는 트리의 루트는 1번이고 1번을 제외한 모든 노드는 부모가 있다.
1번 루트노드로부터 나머지 모든 노드에 도달 가능하다.
출력
x < y인 순서쌍 (x, y)에 대하여 Tx 와 Ty 의 유사도가 같은 경우 이들 순서쌍의 개수를 출력한다.
예제 #1
5
1 2
1 3
1 4
1 5
6
예제 #2
6
1 2
2 3
3 4
1 5
5 6
2
순서쌍(4, 6) 일 때 T4와 T6 는 S(T4, 0)과 S(T6, 0)이 1개씩으로 같으므로 유사도가 같다.
순서쌍(3, 5) 일 때 T3와 T5 는 S(T3, 0)과 S(T5, 0)이 1개씩으로 같고 S(T3, 1)과 S(T5, 1)도 1개씩으로 같으므로 유사도가 같다.
예제 #3
13
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
6 10
7 11
8 12
11 13
14
로그인해야 코드를 작성할 수 있어요.