题目描述

很久以前，在一个很远很远的星系里，有 $n$ 颗行星和 $n−1$ 条连接所有行星的边。换句话说，行星和边形成了一棵树。此外，每条边上都有一个权值。

行星对 $(A,B)$ 是无聊的，当且仅当如下条件成立：

• $A\neq B$。
• 行星 $A,B$ 可以互相到达。
• 行星 $A,B$ 之间的路径上的所有边的权值的异或和等于 $0$。

现在，由于不可控力，该星系的所有边会按一定顺序摧毁。请求出初始时和每次摧毁一条边之后无聊的行星对数量。

输入格式

第一行输入一个整数 $n$，表示行星的数量。
随后 $n-1$ 行，每行三个整数 $a_i,b_i,z_i$，分别表示第 $i$ 条边连接的两个点的编号和第 $i$ 条边的权值。
随后一行输入 $n-1$ 个整数，第 $i$ 个整数 $p_i$ 表示第 $i$ 次摧毁的边的编号。

输出格式

输出 $n$ 行，每行一个整数，其中第 $i$ 个整数表示在按顺序摧毁了 $i-1$ 条边后无聊的行星对数量。

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

提示

【样例 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$		$\times$
$3\sim 4$	$10^5$	$\surd$
$5\sim 10$		$\times$

特殊性质 A：每条边的权值为 $0$。换句话说，$\forall i\in[1,n)$，$z_i=0$。

【题目来源】

本题来源自 COCI 2015-2016 CONTEST 4 T5 GALAKSIJA，按照原题数据配置，满分 $140$ 分。

由 Eason_AC 翻译整理提供。