Problem Description

A long time ago, in a galaxy far, far away, there were $n$ planets and $n-1$ edges connecting all planets. In other words, the planets and edges formed a tree. Also, each edge had a weight.

A planet pair $(A,B)$ is boring if and only if the following conditions hold:

• $A \neq B$.
• Planets $A$ and $B$ can reach each other.
• The xor sum of the weights of all edges on the path between $A$ and $B$ equals $0$.

Now, due to an uncontrollable force, all edges in the galaxy will be destroyed in a fixed order. Please output the number of boring planet pairs at the beginning and after each time an edge is destroyed.

Input Format

The first line contains an integer $n$, the number of planets.
Then follow $n-1$ lines, each containing three integers $a_i, b_i, z_i$, meaning that the $i$-th edge connects nodes $a_i$ and $b_i$, and its weight is $z_i$.
Then a line contains $n-1$ integers; the $i$-th integer $p_i$ indicates the index of the edge destroyed in the $i$-th destruction.

Output Format

Output $n$ lines, each containing one integer. The $i$-th integer denotes the number of boring planet pairs after destroying $i-1$ edges in order.

2
1 2 0
1

1
0

3
1 2 4
2 3 4
1 2

1
0
0

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

6
3
1
0

Hint

[Sample 1 Explanation]

Initially, only the planet pair $(1,2)$ is boring. After destroying the only edge, there are no boring planet pairs anymore.

[Sample 2 Explanation]

Initially, only the planet pair $(1,3)$ is boring. After destroying edge $1$, since planets $1$ and $3$ can no longer reach each other, there are no boring planet pairs afterward.

[Sample 3 Explanation]

Initially, all planet pairs are boring, because for every pair of planets, the xor sum of the weights of all edges on the path between them is $0$.

[Constraints]

For all testdata, $1 \leqslant n \leqslant 10^5$, $1 \leqslant a_i, b_i \leqslant n$, $0 \leqslant z_i \leqslant 10^9$.

There are $10$ test points in total. The constraints for each test point are as follows:

Special Property A: The weight of every edge is $0$. In other words, $\forall i \in [1, n)$, $z_i = 0$.

[Source]

This problem comes from COCI 2015-2016 CONTEST 4 T5 GALAKSIJA. With the original testdata configuration, the full score is $140$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5