#P13825. [apc001]XOR Tree

    ID: 13026 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-异或抵消不变量分析交换论证子集 DP子掩码递推 (s-1)&mask对称性去重

[apc001]XOR Tree

题目描述

给一棵有 NN 个节点的树,节点编号从 00 到 N−1N-1, 树边编号从 11 到 N−1N-1。第 ii 条边连接节点 xix_i 和 yiy_i,其权值为 aia_i。

你可以对树执行任意次操作,每次操作选取一条链和一个非负整数 xx,将链上的边的权值与 xx 异或成为该边的新权值。

问最少需要多少次操作,使得所有边的权值都为 00。

输入格式

第一行有 11 个整数,代表树的节点数 NN。

接下来 N−1N-1 行,每行有 33 个整数,第 i+1i+1 行上的整数分别代表第 ii 条边的参数 xi,yi,aix_i,y_i,a_i。

输出格式

仅一行 11 个整数,即最小操作数。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

2
1 0 0

输出 #2

0

说明/提示

  • 2≤N≤1052\leq N \leq 10^5
  • 0≤xi,yi≤N−10\leq x_i,y_i \leq N-1
  • 0≤ai≤150\leq a_i \leq 15
  • 保证给定的图是一棵树
  • 保证输入数据都是整数