P3359 Transform the XOR Tree

You are given a tree with $n$ nodes, and each edge has a weight. Now we delete all $n - 1$ edges one by one in a given order. After deleting each edge, query how many paths currently have the XOR sum of edge weights equal to $0$.

The first line contains an integer $n$. The next $n - 1$ lines each contain three integers $a_i, b_i, z_i$, with $1 \le a_i, b_i \le n$, indicating that there is an edge with weight $z_i$ between nodes numbered $a_i$ and $b_i$. The next line contains $n - 1$ integers separated by single spaces, which form a permutation of $1 \sim n - 1$, representing the deletion order of the $n - 1$ edges.

Output $n$ lines, each containing one integer. The $k$-th line (where $k = 0, 1, \dots, n - 1$) is the number of paths whose XOR sum of edge weights is $0$ after deleting the first $k$ edges in the given order.

For $20\%$ of the testdata, $n \le 1000$. For another $30\%$ of the testdata, all $z_i = 0$. For all testdata, $n \le 10^5$, $0 \le z_i \le 10^9$. Translated by ChatGPT 5