XOR Zero Paths in a Tree Under Edge Removal

You are given a tree with n nodes and n−1 edges. Each edge has an integer weight. The tree is initially connected. Then, the edges are removed one by one in a given order. After each removal, consider the forest that remains. For every pair of distinct nodes u and v that remain connected in the same tree, there is a unique simple path between them. Let the XOR sum of the weights along that path be \[ b_1 \oplus b_2 \oplus \cdots \oplus b_k, \] where \(\oplus\) denotes the bitwise XOR operation. Your task is to output, after each removal, the number of pairs \((u,v)\) (with \(u < v\)) for which the XOR sum of the path is zero.

Note: The answer after each edge removal should be computed on the current forest.

Hint: It is recommended to process the queries offline in reverse (i.e. add edges back in reverse order) using a disjoint set union (DSU) data structure that maintains extra information to quickly count the number of valid pairs.

inputFormat

The input consists of the following:

• The first line contains an integer n (number of nodes).
• The next n−1 lines each contain three integers u, v, and w, representing an edge between nodes u and v with weight w. The edges are numbered from 1 to n−1 in the order given.
• The next n−1 lines each contain an integer which is the index of the edge to remove at that step.

outputFormat

Output n−1 lines. The i-th line should contain an integer representing the number of pairs (u, v) (with u < v) in the current forest whose path XOR sum equals 0 after the first i edge removals.

sample

3
1 2 1
2 3 1
1
2

0
0

</p>