루트가 있는 트리에서 트리의 깊이를 다음과 같이 정의하자.

1. 루트의 깊이는 0이다.

2. 부모의 깊이가 d라면 그 자식의 깊이는 d + 1이다.

S(T, d) 를 트리 T에서 깊이가 d인 노드의 개수라고 하자. 이때, 두 개의 루트가 있는 트리 T_a과 T_b에서 모든 음이 아닌 정수 d에 대하여

S(T_a, d)와 S(T_b, d)가 같다면 두 트리 T_a과 T_b는 유사도가 같다고 정의한다.

노드의 개수가 N개인 루트가 있는 트리 T가 주어진다. 트리 T의 노드는 1에서 N까지 번호가 매겨져 있으며 루트는 1번이다.

T_k를 노드 k를 루트로 하는 부분트리라고 할 때, i<j인 모든 순서쌍(i, j)에 대하여 T_i와 T_j의 유사도가 같은 쌍의 개수를 구하는 것이 여러분에게 주어진 과제이다.

부분트리 유사도 timer 2s memory 512MB

부분트리 유사도 2s 512MB