Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Similarity of Subtrees

Define the depth of a node in a rooted tree by applying the following rules recursively:

 The depth of a root node is 0.

 The depths of child nodes whose parents are with depth $d$ are $d + 1$.

Let $S(T, d)$ be the number of nodes of $T$ with depth $d$. Two rooted trees $T$ and $T'$ are similar if and only if $S(T, d)$ equals $S(T', d)$ for all non-negative integer $d$.

You are given a rooted tree $T$ with $N$ nodes. The nodes of $T$ are numbered from 1 to $N$. Node 1 is the root node of $T$. Let $T_i$ be the rooted subtree of $T$ whose root is node $i$. Your task is to write a program which calculates the number of pairs $(i, j)$ such that $T_i$ and $T_j$ are similar and $i < j$.

Input

The input consists of a single test case.

$N$

$a_1$ $b_1$

$a_2$ $b_2$

...

$a_{N-1}$ $b_{N-1}$

The first line contains an integer $N$ ($1 \leq N \leq 100,000$), which is the number of nodes in a tree. The following $N -1$ lines give information of branches: the $i$-th line of them contains $a_i$ and $b_i$, which indicates that a node $a_i$ is a parent of a node $b_i$. ($1 \leq a_i, b_i \leq N, a_i \ne b_i$) The root node is numbered by 1. It is guaranteed that a given graph is a rooted tree, i.e. there is exactly one parent for each node except the node 1, and the graph is connected.

Output

Print the number of the pairs $(x, y)$ of the nodes such that the subtree with the root $x$ and the subtree with the root $y$ are similar and $x < y$.

Sample Input 1

5
1 2
1 3
1 4
1 5

Output for the Sample Input 1

6

Sample Input 2

6
1 2
2 3
3 4
1 5
5 6

Output for the Sample Input 2

2

Sample Input 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

Output for the Sample Input 3

14



Sample input:
5
1 2
1 3
1 4
1 5


Sample output:
6

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
import sys
def main():
    readline = sys.stdin.readline
    write = sys.stdout.write
    N = int(readline())
    G = [[] for i in range(N)]
    for i in range(N-1):
        a, b = map(int, readline().split()); a -= 1; b -= 1
        G[a].append(b)
        G[b].append(a)

    H = [-1]*N
    MOD = 10**9 + 9
    X1 = [0]*N; v1 = 13
    X2 = [0]*N; v2 = 17
    U = [0]*N
    que = deque([0])
    U[0] = 1
    D = [0]
    while que:
        v = que.popleft()
        for w in G[v]:
            if U[w]:
                continue
            U[w] = 1
            que.append(w)
            D.append(w)
    M = defaultdict(int)
    for v in reversed(D):
        h = 0
        su1 = su2 = 0
        for w in G[v]:
            if H[w] == -1:
                continue
            h = max(h, H[w])
            su1 += X1[w]; su2 += X2[w]
        H[v] = k = h+1
        X1[v] = w1 = (su1*v1 + 1) % MOD
        X2[v] = w2 = (su2*v2 + 1) % MOD
        M[k, w1, w2] += 1
    ans = 0
    for v in M.values():
        ans += v*(v-1)//2
    write("%d\n" % ans)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

MOD = 10 ** 30 + 7

N = input()
E = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, raw_input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

m = {}

def func(num, pre):
    S = 0
    for to in E[num]:
        if to != pre:
            S += func(to, num)
    S *= 1000000007
    S += 1
    S %= MOD
    if not S in m:
        m[S] = 1
    else:
        m[S] += 1
    return S

func(0, -1)

ans = 0
for key in m:
    ans += m[key] * (m[key] - 1) / 2
print ans