Problem Description

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$.

Input Format

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 Format

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.

4
1 2 0
2 3 0
2 4 0
3 1 2

6
3
1
0

Hint

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