2238C.md (3026B)
1 Source: https://codeforces.com/problemset/problem/2238/C 2 3 C. Village Guilds 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Hmmmrmm. 22 23 — Minecraft 24 25 During his long adventure, Steve stumbled upon a village of villagers. The houses in the village are connected by bidirectional paths. In total, there are $n$ houses in the village, numbered from $1$ to $n$. The graph of houses and paths represents a rooted$^{\text{∗}}$ tree$^{\text{†}}$, rooted at vertex $1$, where the town hall is located. 26 27 Consider an arbitrary house $v$ and its subtree$^{\text{‡}}$. For each such house $v$ and each non-negative integer $h$, consider the set of houses that are in the subtree of $v$ at a distance exactly $h$ from $v$. Such a set will be called a guild. For example, for $h=0$, the guild will consist only of the vertex $v$. 28 29 In the example below, the guilds for the vertex $v=4$ are shown. The guild for $h=0$ is marked in red, for $h=1$ in light blue, and for $h=2$ in green. 30 31  32 33 Two guilds are considered different if there exists a house that is in one guild and not in the other. Steve wants to know how many different non-empty guilds there are in the tree. Help him with this. 34 35 $^{\text{∗}}$A rooted tree is a tree where one vertex is special and called the root. 36 37 $^{\text{†}}$A tree is a connected graph without cycles. 38 39 $^{\text{‡}}$A subtree of vertex $v$ is the subgraph of $v$, all its descendants, and all the edges between them. 40 41 Input 42 43 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 44 45 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of houses in the village. 46 47 The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i \lt i$), where $p_i$ is the parent of the $i$-th house in the tree. 48 49 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 50 51 Output 52 53 For each test case, output a single integer — the number of different guilds in the village. 54 55 Example 56 57 Input 58 59 ``` 60 5 61 62 5 63 64 1 2 3 4 65 66 3 67 68 1 1 69 70 7 71 72 1 2 1 3 5 5 73 74 10 75 76 1 1 3 2 2 4 4 4 3 77 78 15 79 80 1 2 1 3 3 4 3 7 3 10 6 7 1 9 81 ``` 82 83 Output 84 85 ``` 86 5 87 88 4 89 90 9 91 92 15 93 94 22 95 ``` 96 97 Note 98 99 In the first testcase, there are $5$ guilds, each consisting of a single house. 100 101 In the second testcase, in addition to the guilds consisting of a single house, there is also a guild consisting of vertices $2$ and $3$. It can be obtained by considering houses at distance $h=1$ in the subtree of vertex $v=1$. 102 103 In the third testcase, in addition to the guilds consisting of a single house, there are $2$ more guilds: for $v=1$ and $h=1$, the guild consists of vertices $2$ and $4$; for $v=5$, $h=1$, the guild consists of vertices $6$ and $7$. 104 105 