Problem Description

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

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

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

Now, due to uncontrollable forces, all edges in the galaxy will be destroyed in a certain order. You are asked to find the number of boring planet pairs initially and after each edge is destroyed.

Input Format

The first line contains an integer $n$, representing the number of planets.
The next $n-1$ lines each contain three integers $a_i, b_i, z_i$, representing the two endpoints of the $i$-th edge and its weight.
The last line contains $n-1$ integers, where the $i$-th integer $p_i$ represents the index of the edge to be destroyed in the $i$-th step.

Output Format

Output $n$ lines, each containing an integer. The $i$-th integer represents the number of boring planet pairs after $i-1$ edges have been destroyed.

Sample Input and Output

Input Sample #1

2
1 2 0
1

Output Sample #1

1
0

Input Sample #2

3
1 2 4
2 3 4
1 2

Output Sample #2

1
0
0

Input Sample #3

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

Output Sample #3

6
3
1
0

Notes

[Sample 1 Explanation]

Initially, only the planet pair $(1, 2)$ is boring. After the only edge is destroyed, no boring planet pairs exist.

[Sample 2 Explanation]

Initially, only the planet pair $(1, 3)$ is boring. After the first edge is destroyed, since planets $1$ and $3$ cannot reach each other, no boring planet pairs exist afterward.

[Sample 3 Explanation]

Initially, all planet pairs are boring because the XOR sum of the weights of all edges on the path between any two planets is $0$.

[Data Range]

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

This problem consists of $10$ test cases, and the data range for each test case is as follows:

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

[Problem Source]

This problem is from COCI 2015-2016 CONTEST 4 T5 GALAKSIJA, configured according to the original problem data, with a full score of $140$.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分