問題文
田桥喜欢桥梁。因此,我喜欢称为树的图,其中每条边都是一座桥(图论术语)。另外,Tahashi 最近在学校学习了 XOR。所以我在思考以下问题:
N 顶点和 N-1 我们得到一个由书本边组成的连通无向图或树。每个顶点都是一个顶点 它被称为 1、頂点 2、…、頂点 N 。每条边都分配有一个非负整数成本。 给出了
整数 X ,所以顶点 a 和顶点 连接 b 的简单路径(不会两次通过同一条边的路径;在树中,它总是 1 上边缘(仅存在一个)的成本为\rm{xor}日语 X 求 (a,b) (1≦a<b≦N的总数。 然而\rm{xor}总和是几个整数 A_1,A_2,… ,其二进制表示的按位异或 表示通过 A_1 \rm{xor} A_2 \rm{xor}… 获得的值。 例如,1 \rm{xor} 2 \rm{xor} 5 是 给出了 6 。
你的工作就是为 Tahashi 解决这个问题。
入力
输入是按以下格式从标准输入给出的。
N X
x_1 y_1 c_1
x_2 y_2 c_2
:
x_{N-1} y_{N-1} c_{N-1}
- 1 行包含一个整数,表示图中的顶点数。 N (1 ≦ N ≦ 100,000) 和问题文本中的整数 X (0≦X≦10^9) 。 来自行
- 继续 N-1 行包含图形的 N-1 提供了有关本书侧面的信息。其中 i(1≦i≦N-1) 行中,i 第一条边连接 2 顶点 x_i,y_i(1≦x_i,y_i≦N) 和成本 c_i (0≦c_i≦10^9) 。 来自行
- 保证给定的图是连通的。
出力
1 输出第 1 行问题陈述中所需的答案。在末尾插入换行符。 当
入力例1
6 7 1 2 5 2 3 3 3 4 6 2 5 2 5 6 7
出力例1
3
(a,b)=(1,5),(4,5),(5,6) 时,路径上边的成本为\rm{xor}日语 7(2采用十六进制表示法111),所以答案是 3 变为。
此输入示例的图表如下所示。至于成本,10十六进制表示法和2显示十进制。 以上
入力例2
6 3 1 2 1 2 3 3 3 4 2 4 5 3 4 6 1
出力例2
4
入力例3
10 1 9 10 1 6 10 1 5 2 1 8 6 1 4 5 1 7 6 0 3 8 0 3 1 1 8 2 0
出力例3
25