P9745「KDOI-06-S」树上异或位运算trick+树形dp看到题目中贡献的计算，可以想到乘法分配律，也就是一个连通块的乘积可以直接乘在当前所有方案的权值之和上。可以考虑特殊性质：链。那么树的问题就变成了序列问题。容易设\(f_i\)表示\(i\)以前的节点的所有断边方案权值和。转移

Solution树形DP好题。PartI部分分类比下文为简单，我们称一个连通块的权值为连通块内点的异或和。考虑链的部分分，显然可以设\(f_{i}\)是前\(i\)个点所有断边方案的权值和，对于每个点枚举上一条断的边转移。令\(s_i=\bigoplus_{j=1}^{i}a_j\)，则\(f_i=\sum_{j=0}^{i-1}(s

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

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

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