题目描述

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

输入格式

第一行一个整数n。

接下来n-1 行，每行三个整数ai，bi， zi，满足1<= ai， bi <=n，表示树上编号为ai 的点和编号为bi 的点中间连有一条权值为zi 的边。

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

输出格式

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

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

6
3
1
0

提示

对于20% 数据，满足n <= 1000。

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

对于全部数据，满足n <=10^5，0<= zi<= 10^9。