ZOJ Problem Set - 4073
Chiaki has a rooted tree with $n$ nodes numbered $1$ to $n$. The root is node $1$. Each edge has a positive integer weight on it.
Now, two players are playing a game on the tree. They play the game in turn. In each turn, the player should choose an edge and decrease its weight by $1$.
If an edge's weight becomes $0$, it will be removed. After an edge is removed, the tree will be split into two parts. The part without the root node should be discarded (i.e. permanently removed from the tree).
If in a turn, a player has no edge left to choose, he loses the game.
Chiaki, as the player with the first turn, would like to know which edges she can choose at the first turn, to make sure she will win?
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^6$) -- the number of nodes in the tree.
Each of the next $n-1$ lines contains two integers $p_i$ and $w_i$ ($2 \le i \le n$, $1 \le p_i \le n$, $1 \le w_i \le 10^9$) where $p_i$ denotes the parent of the $i$-th node and $w_i$ is the weight of the edge between $i$ and $p_i$.
It's guaranteed that the sum of $n$ in all test cases will not exceed $10^6$.
For each test case, output two lines.
The first line is a single number $m$, the number of edges Chiaki can choose at the first move to make sure Chiaki will win.
The second line contains $m$ increasing numbers separated with one space. Output the number $u$ means you can choose the edge between node $u$ and its parent.
3 5 1 2 1 2 1 2 1 1 5 1 2 1 2 1 2 1 2 5 1 1 2 1 3 1 4 1
4 2 3 4 5 0 1 2
Author: LIN, Xi
Source: Yet Another Xi Lin Contest