P8047 [COCI 2015/2016 #4] GALAKSIJA

很久以前，在一个很远很远的星系里，有 $n$ 颗行星和 $n−1$ 条连接所有行星的边。换句话说，行星和边形成了一棵树。此外，每条边上都有一个权值。 行星对 $(A,B)$ 是**无聊的**，当且仅当如下条件成立： - $A\neq B$。 - 行星 $A,B$ 可以互相到达。 - 行星 $A,B$ 之间的路径上的所有边的权值的**异或和**等于 $0$。 现在，由于不可控力，该星系的所有边会**按一定顺序**摧毁。请求出初始时和每次摧毁一条边之后**无聊的**行星对数量。

无

无

**【样例 1 解释】** 初始时，只有行星对 $(1,2)$ 是无聊的。在毁坏了唯一的一条边之后，就不再存在无聊的行星对了。 **【样例 2 解释】** 初始时，只有行星对 $(1,3)$ 是无聊的。在破坏了 $1$ 号边之后，由于行星 $1,3$ 之间不能互相到达，因此之后不再存在无聊的行星对了。 **【样例 3 解释】** 初始时，所有的行星对都是无聊的，因为所有行星对中的两个行星之间的路径上的所有边的权值的异或和是 $0$。 **【数据范围】** 对于所有数据，$1\leqslant n\leqslant 10^5$，$1\leqslant a_i,b_i\leqslant n$，$0\leqslant z_i\leqslant 10^9$。 本题一共 $10$ 个测试点，每个测试点的数据范围如下： | 测试点 | $n\leqslant $ | 特殊性质 A | | :-----------: | :-----------: | :-----------: | | $1$ | $1000$ | $\surd$ | | $2$ | $1000$ | $\times$ | | $3\sim 4$ | $10^5$ | $\surd$ | | $5\sim 10$ | $10^5$ | $\times$ | 特殊性质 A：每条边的权值为 $0$。换句话说，$\forall i\in[1,n)$，$z_i=0$。 **【题目来源】** 本题来源自 **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T5 GALAKSIJA_**，按照原题数据配置，满分 $140$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。