Black and White Tree
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has a rooted tree, consisting of N vertexes. Each tree vertex has a unique index (integer from 1 to N), and also has a color (black or white).
The root of Chef's tree has index 1.
Initially, all vertexes of the tree are colored white. Then Chef start playing with the tree. He writes out a sequence of
M vertexes of the tree V1, V2, ..., VM. And now he wants to make M operations with the tree, each of them is:
- During i-th operation Chef picks vertex Vi.
- If vertex Vi is black, then he colors it white.
- Chef finds the farthest white vertex from vertex Vi, in case of tie he picks the one with largest index. This vertex is the result of current operation.
- If vertex Vi wasn't recolored on step 2 of current operation (therefore before the operation it is white), Chef colors it black.
Chef gives to you the tree and sequence V. Help him to make all the operations. So, print the index of resulting vertex for each operation.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N, M - the number of vertexes of the tree and the number of operations.
The second line contains N-1 integers P2, P3, ..., PN - description of Chef's tree.
Integer Pi denotes the index of vertex that is parent of the vertex i in the tree.
Each of the next M lines contains the description of operations, i-th of them contains integer Vi.
It is guaranteed that the given graph is a tree.
For each operation of each test case print the index of resulting vertex on the separate line.
1 ≤ T ≤ 1000,
2 ≤ N ≤ 200000,
1 ≤ M ≤ 200000,
1 ≤ Pi, Vi ≤ N;
Sum of all N values for test cases is not greater than 200000.
Sum of all M values for test cases is not greater than 200000.
Input: 2 6 7 3 1 3 4 4 1 5 6 1 3 5 2 2 2 1 2 1 Output: 6 2 2 4 4 2 5 1 1
|Tags||data-structure, gerald, hard, heavy-light, nov13|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.