题目描述

给定一棵 $n$ 个点的树，每条边上都有一个权值。现在按顺序删掉所有的 $n-1$ 条边，每删掉一条边询问当前有多少条路径满足路径上所有边权值异或和为 $0$。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行三个整数 $a_i,b_i,z_i$，满足 $1\le ai,bi\le n$，表示树上编号为 $a_i$ 的点和编号为$b_i$ 的点中间连有一条权值为 $z_i$ 的边。

接下来一行 $n-1$ 个整数，两两之间有一个空格隔开，表示一个 $1\sim n- 1$ 的排列，表示 $n - 1$ 条边的删边顺序。

输出格式

输出 $n$ 行，每行一个整数，依次表示删掉第 $0\sim n - 1$ 条边之后的边权异或和为零的路径数。

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

6
3
1
0

提示

对于 $20\%$ 数据，满足 $n\le 1000$。

对于另外 $30\%$ 数据，满足所有的 $z_i = 0$。

对于全部数据，满足 $n\le 10^5,0\le z_i\le 10^9$。