{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003e\u003c/h2\u003e\n\n\u003cp\u003e\nDefine the depth of a node in a rooted tree by applying the following rules recursively:\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e The depth of a root node is 0.\u003c/li\u003e\n\u003cli\u003e The depths of child nodes whose parents are with depth $d$ are $d + 1$.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nLet $S(T, d)$ be the number of nodes of $T$ with depth $d$. Two rooted trees $T$ and $T\u0027$ are similar if and only if $S(T, d)$ equals $S(T\u0027, d)$ for all non-negative integer $d$.\n\u003c/p\u003e\n\n\u003cp\u003e\nYou 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 \u0026lt; j$.\n\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\nThe input consists of a single test case.\u003cbr\u003e\n\u003cbr\u003e\n$N$\u003cbr\u003e\n$a_1$ $b_1$\u003cbr\u003e\n$a_2$ $b_2$\u003cbr\u003e\n...\u003cbr\u003e\n$a_{N-1}$ $b_{N-1}$\n\u003c/p\u003e\n\n\u003cp\u003e\nThe 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.\n\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e\nPrint 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 \u0026lt; y$.\n\u003c/p\u003e\n\n\u003ch3\u003eSample Input 1\u003c/h3\u003e\n\u003cpre\u003e5\n1 2\n1 3\n1 4\n1 5\n\u003c/pre\u003e\n\n\u003ch3\u003eOutput for the Sample Input 1\u003c/h3\u003e\n\u003cpre\u003e6\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Input 2\u003c/h3\u003e\n\u003cpre\u003e6\n1 2\n2 3\n3 4\n1 5\n5 6\n\u003c/pre\u003e\n\n\u003ch3\u003eOutput for the Sample Input 2\u003c/h3\u003e\n\u003cpre\u003e2\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Input 3\u003c/h3\u003e\n\u003cpre\u003e13\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n4 8\n4 9\n6 10\n7 11\n8 12\n11 13\n\u003c/pre\u003e\n\n\u003ch3\u003eOutput for the Sample Input 3\u003c/h3\u003e\n\u003cpre\u003e14\n\u003c/pre\u003e"}}]}