Path

有一棵 \(n\) 个点的树，树的边上有权值，定义一个路径为好的当且仅当这条路径上所有边的权值的异或和等于 \(0\) ( \(x\) 到 \(y\) 的路径和 \(y\) 到 \(x\) 的路径被视作是相同的路径) 。

现在要按照一个次序把这棵树里的所有边删掉，请输出所有删除操作开始前的这棵树的好路径条数以及每次删除操作之后的树的好路径条数。

输入格式
第一行一个整数 \(n\) 。

接下来的 \(n?1\) 行，每行三个整数 \(x_i,y_i,z_i\) 表示点 \(xi\) 和点 \(y_i\) 之间有一条权值为 $z_i $的边。

接下来的一行， \(n?1\) 个整数，第 \(i\) 个整数 \(p_i\) 表示删除操作中第 \(i\) 次要删除的边是 \((x_{p_i},y_{p_i},z_{p_i})\) 。（即读入中的第 \(p_i\) 条边）

输出格式
输出共 \(n\) 行。

第一行输出所有删除操作开始前这棵树的好路径条数。

第 \(i\) 行输出第 \(i?1\) 次删除操作之后的树的好路径条数。

样例
input

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

output

6
3
1
0

数据范围
时间限制: \(3s\)
空间限制: \(256MB\)
对于 \(20\%\) 的数据， \(n\le10^3\) 。
对于另外 \(20\%\) 的数据， \(z_i=0\) 。
对于 \(100\%\) 的数据， \(n\le10^5,0\le zi\le10^9\) 。

注:后面用\(\bigoplus\)表示异或。

首先先看一下如何求一条路径的所有边有异或和呢？我们可以预处理从根节点到\(i(1\le i\le n)\)的边权异或和\(f_i\)，两个点\(u,v\)之间路径的异或和就是\(f_u\bigoplus f_v\)。本题问有多少个路径异或和为0，就是问有多少个\(f_u\)和\(f_v\)相等。
这题叫我们删边，一般删边是很难处理的。所以我们考虑反着来，也就是加边。一开始有\(n\)个点，答案是0。尝试实时维护现在找到的路径数量。

现在假设我们考虑到了一条由\(u\)到\(v\)的长度为\(w\)的边。
由于我们是加边，所以之前找到的路径现在加完边依然存在。所以我们只需要考虑加完这条边后会有多少个新的点到达根节点的值相等。我们可以把每颗树设一个根节点，每个点存下他到根节点的路径边权异或和。当连完一条边后，到达根节点的距离会怎么变化呢。

我们现在不妨先将\(u\)的这颗树合并到\(v\)上。设\(v\)的根节点是\(p\)。枚举u这颗树树上的所有点\(x\)，先把x的根节点标为\(p\),点\(p\)到\(u\)的路径异或和为\(f_v\bigoplus w\),点\(x\)到\(p\)的异或和还要异或上\(u\)到\(x\)的异或和，也就是\(f_u\bigoplus f_x\).所以$f_x=f_v\bigoplus f_u\bigoplus w\bigoplus f_x $ 然后我们对每个子树建一个map，统计v的子树上有多少个和\(f_x\)相同的，这就是新的合法路径，维护答案就可以了。

但是这个复杂度明显爆炸，然而我们可以加上几行的代码。定义\(sz_x\)为以x为根的大小。每次我们将子树小的合并到子树大的，然后复杂度就变成了启发式合并。再套个map，总复杂度\(O(nlog^2n)\)

#pragma GCC optimize(2)
#include
#include
#include