Boring Planet Pairs

A long time ago in a galaxy far, far away there were $N$ planets. There were also $N-1$ interplanetary paths, and those paths connected every planet directly or indirectly. In other words, the planets and the paths form a tree. Each path carries one integer, the curiosity of that path.

A pair of planets $A$, $B$ is boring when all three conditions hold.

• $A$ and $B$ are different planets.
• You can travel from $A$ to $B$ along one or more interplanetary paths.
• The binary XOR of the curiosity of every path on that travel is $0$.

The pair $(A, B)$ and the pair $(B, A)$ count as the same pair.

Times have changed and an evil emperor now rules the galaxy. He uses the Force to destroy all the interplanetary paths in a fixed order. Count the boring pairs before the destruction starts and after each destruction.

The first line contains the number of planets $N$. ($1 \le N \le 100\,000$)

Each of the next $N-1$ lines contains three integers $A_i$, $B_i$, $Z_i$ separated by spaces, which mean that planet $A_i$ and planet $B_i$ are directly connected by a path of curiosity $Z_i$. ($1 \le A_i, B_i \le N$, $0 \le Z_i \le 1\,000\,000\,000$)

The last line contains a permutation of the integers from $1$ to $N-1$. If the $i$-th value of the permutation is $j$, the emperor destroys the $j$-th path of the input at step $i$. When $N = 1$, this line contains no numbers.

Print $N$ lines. The $k$-th line holds the number of boring pairs left after exactly $k-1$ paths are destroyed.

In the first example the pair of planets $1$ and $2$ is boring before the destruction. Once the path is destroyed, no route connects them.

In the second example the pair $(1, 3)$ is boring before the destruction. After the first destruction and after the second one, travel between planet $1$ and planet $3$ is impossible, and none of the remaining pairs is boring.

In the third example every path has curiosity $0$, so every pair of planets that still has a route between them is boring.