codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/a938038658faae022f04ae6bbab854fdb13fcf9f.png) 
     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  ![](https://espresso.codeforces.com/8b4347ae961535dc26e91f46a38b1f15c3b2e6e1.png)