Internet Problem Solving Contest

IPSC 2014

Problem I – Intrepid cave explorer

Maru likes to visit new places, but with her poor sense of direction she always struggles to find her way home. This summer, she’s planning to explore an amazing lava cave. Your task is to help her mark the chambers in the cave so that she won’t get lost.

Problem specification

The cave consists of n chambers numbered 1 through n. There are n − 1 passages, each connecting a pair of chambers in such a way that the entire cave is connected. (Hence, the topology of the cave is a tree.) Chamber 1 contains the entrance to the cave.

Chamber u is an ancestor of chamber v if u lies on the path from v to the entrance. (In particular, each chamber is its own ancestor, and chamber 1 is an ancestor of every chamber.) For any chamber v ≠ 1, the ancestor of v that is directly adjacent to v is denoted pv and called the parent of v. Chamber numbers are chosen in such a way that for all v ≠ 1, pv < v.

Maru has two pieces of chalk: a white one and a pink one. She wants to mark each chamber in the cave with some (possibly empty) string of white and pink dots. These strings must satisfy the following requirements:

(The empty string is a prefix of any string. Each string is its own prefix. Note that we do not require the strings assigned to chambers to be pairwise distinct.)

Find a valid assignment of strings to chambers that minimizes the total number of chalk dots.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case describes a tree. In the first line there is an integer n – the number of chambers. The second line contains n − 1 integers p2, p3, , pn where pi is the parent of chamber i (1 ≤ pi < i).

In the easy subproblem I1, we have 2 ≤ n ≤ 150, and no chamber is the parent of more than 20 chambers. In the hard subproblem I2 we have 2 ≤ n ≤ 21 000.

Output specification

For each test case, output one line with one integer – the smallest possible number of dots Maru has to draw in the cave in order to properly mark all chambers.




1 1 3 3



Using W and P to denote white and pink dots, respectively, one optimal labeling looks as follows: 1 → “” (i.e., an empty string), 2 → W”, 3 → P”, 4 → PW”, 5 → PP”.