1/23/25, 7:29 PM Problem - 2031E - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 987 (Div. 2)
E. Penchick and Chloe's Trees Finished
time limit per test: 3.5 seconds Practice
memory limit per test: 512 megabytes
With just a few hours left until Penchick and Chloe leave for Singapore, they could hardly wait to
see the towering trees at the Singapore Botanic Gardens! Attempting to contain their excitement,
Penchick crafted a rooted tree to keep Chloe and himself busy. → Virtual participation
Virtual contest is a way to take part in past contest,
Penchick has a rooted tree∗ consisting of n vertices, numbered from 1 to n , with vertex 1 as the as close as possible to participation on time. It is
root, and Chloe can select a non-negative integer d to create a perfect binary tree† of depth d. supported only ICPC mode for virtual contests. If
you've seen these problems, a virtual contest is not
for you - solve these problems in the archive. If you
Since Penchick and Chloe are good friends, Chloe wants her tree to be isomorphic‡ to just want to solve some problem from a contest, a
virtual contest is not for you - solve this problem in
Penchick's tree. To meet this condition, Chloe can perform the following operation on her own the archive. Never use someone else's code, read
the tutorials or communicate with other person
tree any number of times: during a virtual contest.
Select an edge (u, v), where u is the parent of v. Start virtual contest
Remove vertex v and all the edges connected to v, then connect all of v's previous children
directly to u .
In particular, doing an operation on an edge (u, v) where v is a leaf will delete vertex v without
→ Clone Contest to Mashup
adding any new edges.
→ Submit?
Since constructing a perfect binary tree can be time-consuming, Chloe wants to choose the
minimum d such that a perfect binary tree of depth d can be made isomorphic to Penchick's tree Language: GNU G++20 13.2 (64 bit, winlibs)
using the above operation. Note that she can't change the roots of the trees.
Choose
Choose File No file chosen
∗
A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root. file:
The parent of vertex v is the first vertex on the simple path from v to the root. The root has no parent. A child of
Submit
vertex v is any vertex u for which v is the parent. A leaf is any vertex without children.
†
A full binary tree is rooted tree, in which each node has 0 or 2 children. A perfect binary tree is a full binary tree in
which every leaf is at the same distance from the root. The depth of such a tree is the distance from the root to a
leaf. → Contest materials
‡
Two rooted trees, rooted at r 1 and r 2 respectively, are considered isomorphic if there exists a permutation p of
the vertices such that an edge (u, v) exists in the first tree if and only if the edge (pu , pv ) exists in the second Announcement (en)
tree, and pr = r 2 .
1
Tutorial (en)
Input
Each test contains multiple test cases. The first line contains the number of test cases t (
1 ≤ t ≤ 10
5
). The description of the test cases follows.
6
The first line of each test case contains a single integer n (2 ≤ n ≤ 10 ) — the number of
vertices in Penchick's tree.
The second line of each test case contains n − 1 integers p 2 , p 3 , … , p n (1 ≤ pi ≤ i − 1 )—
the parent of vertex i .
It is guaranteed that the sum of n over all test cases does not exceed 106 .
Output
For each test case, output a single integer on each line: the minimum depth of Chloe's perfect
binary tree.
Example
input Copy
5
6
1 2 2 1 1
15
1 1 2 2 3 3 4 4 5 5 6 6 7 7
5
1 2 2 2
7
1 1 2 1 1 2
10
1 1 1 2 2 2 4 3 3
[Link] 1/2
1/23/25, 7:29 PM Problem - 2031E - Codeforces
output Copy
2
3
3
3
3
Note
For the first test case, create a perfect binary tree with depth 2 .
Consider carrying out the operation on edge AC . Then the edges AC , C F , and C G are
removed, and edges AF and AG are added.
The resulting tree is isomorphic to the tree given in the input. It can be proven that no sequence
of operations carried out on a binary tree of depth less than 2 can lead to a tree isomorphic to the
tree given in the input.
In the second test case, the tree is already isomorphic to a perfect binary tree of depth 3 .
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jan/23/2025 11:34:14UTC+5 (i2).
Desktop version, switch to mobile version.
Privacy Policy
Supported by
[Link] 2/2