← 返回题目列表

AtCoder · arc045_c

C. X或田桥君

中文机器翻译题面 查看原题

問題文

田桥喜欢桥梁。因此,我喜欢称为树的图,其中每条边都是一座桥(图论术语)。另外,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显示十进制。 以上

サンプル1説明

入力例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