P8047 [COCI 2015/2016 #4] GALAKSIJA

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.

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 $n$ lines, each containing one integer. The $i$-th integer denotes the number of **boring** planet pairs after destroying $i-1$ edges in order.

**[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: | Test Point | $n \leqslant$ | Special Property A | | :-----------: | :-----------: | :-----------: | | $1$ | $1000$ | $\surd$ | | $2$ | $1000$ | $\times$ | | $3 \sim 4$ | $10^5$ | $\surd$ | | $5 \sim 10$ | $10^5$ | $\times$ | 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](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T5 GALAKSIJA_**. With the original testdata configuration, the full score is $140$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5