D8.md

D7.T1 AtCoder - apc001_f

题意：

给定一棵 $N$ 个点的树（下标从 $0$ 开始），第 $i$ 条边连接 $x_i,y_i$，边权为 $a_i$。 每次操作选择一条简单路径和一个非负整数 $x$，然后把这条路径上的所有边的边权 XOR $x$。 求把所有边的权值都变为 $0$ 的最小操作次数。

题解：

套路不足，思维不余，这是我的问题。

看到链上修改，可以树上差分。设每个点的为它父亲连向它的边的边权，$d_u$ 为差分数组，那么有： $$ a_u=\bigoplus_{v\in son_u}a_v \wedge d_u\ \ \ \Rightarrow\ \ \ d_u=\bigoplus_{(u,v)\in G}a_v $$ 那么现在我可以每次异或一对点，问把每个点都消为 $0$ 的最小操作次数；首先先把相同的两两消掉，现在 $1\sim 15$ 各自最多剩下一个，状压 DP 解决剩余问题就行了。