9745

感觉是那种，看到题就能猜到大概思路的题。 首先给题目条件增加限制：考虑 \(x_i\leq 7\) 的时候怎么做。这启示我们思考一个和值域相关的做法。 很容易想到一个树形 dp：设 \(dp_{u,i}\) 为在以 \(i\) 为根的子树中，\(u\) 所在连通块异或和为 \(i\) 时方案数与其他 ......

P9745 「KDOI-06-S」树上异或 参考：https://www.luogu.com.cn/blog/710100/p9745-kdoi-06-s-shu-shang-yi-huo-jian-yao-ti-xie 其中，转移中一部分考虑的是断边，那么两部分分离，乘法原理；如果连边，需要异或为 ......

原题 挺好的树形 dp ，正好 dp 不太熟练，练习一下 赛时只想到了暴力和\(X \leq 7\) 的链的部分分，过于 naive 不说了 先考虑链的情况，既然是二进制考虑按位拆分。设 \(g_{i,j,0/1}\) 表示以 \(i\) 为根，从 \(i\) 点连通块的疑惑和第 \(j\) 位为 ......

P9745 「KDOI-06-S」树上异或 题解 \(x_i = 0\) 这题一看就不是很可做，先考虑部分分。 对于一条链的情况，我们可以枚举上一个断边的位置，然后转移。 一看数据范围，估计和值域有关，所以考虑 \(x_i = 1\) 的部分分，如果全部点权都是 1，那么一种方案只有 0 和 1 两 ......