Tree Infection solution codechef
A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex two operations, the spreading operation and, after that, the injection operation:(different from root) is the previous to vertex on the shortest path from the root to the vertex . Children of the vertex are all vertices for which is the parent. You are given a rooted tree with vertices. The vertex is the root. Initially, all vertices are healthy. Each second you do
- Spreading: for each vertex , if at least one child of is infected, you can spread the disease by infecting at most one other child of of your choice.
- Injection: you can choose any healthy vertex and infect it.
InputThe input consists of multiple test cases. The first line contains a single integer ( ) — the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer ( ) — the number of the vertices in the given tree. The second line of each test case contains integers ( ), where is the ancestor if the -th vertex in the tree. It is guaranteed that the given graph is a tree. It is guaranteed that the sum of over all test cases doesn’t exceed .
OutputFor each test case you should output a single integer — the minimal number of seconds needed to infect the whole tree.
5 7 1 1 1 2 2 4 5 5 5 1 4 2 1 3 3 1 6 1 1 1 1 1
4 4 2 3 4
NoteThe image depicts the tree from the first test case during each second. A vertex is black if it is not infected. A vertex is blue if it is infected by injection during the previous second. A vertex is green if it is infected by spreading during the previous second. A vertex is red if it is infected earlier than the previous second.