标签：P9745 06 leftarrow 二进制 题解 times cases dp
原题
- 挺好的树形 dp ，正好 dp 不太熟练，练习一下
- 赛时只想到了暴力和\(X \leq 7\) 的链的部分分，过于 naive 不说了
- 先考虑链的情况，既然是二进制考虑按位拆分。设 \(g_{i,j,0/1}\) 表示以 \(i\) 为根，从 \(i\) 点连通块的疑惑和第 \(j\) 位为 \(0/1\) ，除去连通块部分的积的和。然后设 \(f_i\) 表示以 \(i\) 为根的答案。
- 初始状态：若 \(a_u\) 的第 \(i\) 位为 \(1\) ，则 \(g_{u,i,1} = 1\) ，否则为 \(0\)
- 对于每个儿子，枚举二进制下每位 \(i\) 转移
\[\begin{cases}
g_{i,j,0} \leftarrow g_{i,j,0} \times (g_{i-1,j,0} + f_{i-1}) + g_{i,j,1} \times g_{i-1,j,1} \\
g_{i,j,1} \leftarrow g_{i,j,1} \times g_{i-1,j,0} + g_{i,j,1} \times (g_{i-1,j,0} + f_{i-1}) \\
f_{i} = \sum\limits_{j=0}^{63} 2^j \times g_{i,j,1}
\end{cases}
\]
- 链是相对比较好理解的，然后考虑树的部分。
- 同理的， dp 的定义和链相同，初始状态相同。对于每个儿子，枚举二进制下每位 \(i\) 转移
\[\begin{cases}
g_{u,i,0} \leftarrow g_{u,i,0} \times (g_{v,i,0} + f_{v}) + g_{v,i,1} \times g_{v,i,1} \\
g_{v,i,1} \leftarrow g_{u,i,0} \times g_{v,i,1} + g_{u,i,1} \times (g_{v,i,0} + f_{v}) \\
f_{u} = \sum\limits_{i=0}^{63} 2^i \times g_{u,i,1}
\end{cases}
\]
最终复杂度 \(O(n \log X)\)
标签：P9745,
06,
leftarrow,
二进制,
题解,
times,
cases,
dp
From： https://www.cnblogs.com/fox-konata/p/17775569.html