There is a rooted tree of n vertices with the root in vertex 1, each vertex has zero or one heavy child
li
nked with a heavy edge, a set of maximal connected heavy edges form a heavy chain. A single vertex
can also form a heavy chain, so each vertex belongs to exactly one heavy chain.
Now we want to build a search tree to maintain some information of the original tree. For each heavy
chain with k vertices, we construct a segment tree of depth dlog2 2ke to maintian it, with each leaf of
the segment tree indicating a vertex on the heavy chain, and the parent of the segment tree’s root is the
parent of the top vertex of the heavy chian.
Note that in our variant of the segment tree, every leaves have the same depth.
For instance, this is a possible original tree, note that a double slash indicating a heavy edge.
1
// \
2 7
// \\
3 8
// \\
4 9
// \
5 10
/
6
There are 4 heavy chain in this tree. They are: 1 → 2 → 3 → 4 → 5 , 6 , 7 → 8 → 9, 10
This is the search tree of the previous origin tree, note that the double slash here has no special meaning,
just make the search tree looks more beautiful.
o
// \\
o o
// \\ //
o o o
/ \ / \ /
1 2 3 4 5
| | |
o 10 6
/ \
o o
/ \ /
7 8 9
Given such a original tree, your task is to calculate the depth of the search tree.
The depth of the root is 1.