← 返回题目列表

AtCoder · apc001_f

F. 异或树

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

分数: 1000 点

问题陈述

你得到了一棵树 N 顶点。顶点已编号 0 通过 N-1,并且边缘已编号 1 通过 N-1。 边缘 i 连接顶点 x_i 和 y_i,并且有一个值 a_i。 您可以多次执行以下操作:

  • 选择一个简单路径和一个非负整数 x,然后对于每条边 e 所属路径,更改 a_e 通过执行 a_e ← a_e ⊕ x (⊕表示异或)。

你的目标是 a_e = 0 对于所有边缘 e。 找出实现该目标所需的最少操作数。

约束

  • 2 ≤ N ≤ 10^5
  • 0 ≤ x_i,y_i ≤ N-1
  • 0 ≤ a_i ≤ 15
  • 给定的图是一棵树。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1 a_1
x_2 y_2 a_2
:
x_{N-1} y_{N-1} a_{N-1}

输出

找出实现目标所需的最少操作数。


示例输入 1

5
0 1 1
0 2 3
0 3 6
3 4 4

示例输出 1

3

该目标可以通过以下三个操作来实现:

  • 首先选择连接Vertex的路径 1, 2,和 x = 1.
  • 然后,选择连接Vertex的路径 2, 3,和 x = 2.
  • 最后选择连接Vertex的路径 0, 4,和 x = 4.

示例输入 2

2
1 0 0

示例输出 2

0