题解 P3781 【[SDOI2017]切树游戏】

· · 题解

切树游戏

题目传送门

题目大意

给出一个n个点的树，有m次操作，每次要么查询有多少棵子树异或之和为k,k为每次给出的常数，要么修改一个点的权值。

前置定义

下面我们统称son_u为u的儿子，wson_u为u的重儿子。FWT[a_u]表示只有A[a_u]=1的FWT[A]，树以1为根。

思路

本来想看题解的，但是发现题解看不懂，于是只好自己想，但是发现还是很好想的，只是代码有那么亿点难调。。。

首先，看到异或之和我们显然得想到\texttt{FWT}（不会的可以戳这里学习一下）。我们如果设:

nf[u]=FWT[a_u]

再设f[u]表示以u为根的答案（\texttt{IFWT}之前的），那么可以得到:

f[u]=nf[u]\prod_{v\in son_u}(f[v]+1)

这个非常显然。

最后的答案（\texttt{IFWT}之前）就是:

\sum_{i=1}^{n} f[u]

如果我们设:

s[u]=f[u]+\sum_{v\in son_u} s[v]

那么，答案就是s[1]。

我们发现这个式子非常简洁，于是我们可以联想到动态dp，我们于是可以设:

lf[u]=nf[u]\prod_{v\in son_u\wedge v\not= wson_u} (f[v]+1) ls[u]=\sum_{v\in son_u\wedge v\not= wson_u} s[v]

就可以得到:

f[u]=lf[u](f[wson_u]+1) s[u]=ls[u]+s[wson_u]+f[u] =ls[u]+s[won_u]+lf[u]f[wson_u]+lf[u]

我们将上面的式子用矩阵表示出来，就是:

\begin{bmatrix}lf[u]&0&lf[u]\\lf[u]&1&lf[u]+ls[u]\\0&0&1\end{bmatrix}\begin{bmatrix}f_{wson_u}\\s_{wson_u}\\1\end{bmatrix}=\begin{bmatrix}f_u\\s_u\\1\end{bmatrix}

于是，我们就可以用树链剖分维护这个东西。但是这个矩阵巨大的常数27会让我们\texttt{GG}得很惨。

我们可以看到这样一个神奇的事情:

\begin{bmatrix}a_1&0&b_1\\c_1&1&d_1\\0&0&1\end{bmatrix}\begin{bmatrix}a_2&0&b_2\\c_2&1&d_2\\0&0&1\end{bmatrix}=\begin{bmatrix}a_1a_2&0&a_1b_2+b1\\a_2c_1+c2&1&c_1b_2+d_2+d_1\\0&0&1\end{bmatrix}

于是，我们就只需要维护a_1,b_1,c_1,d_1，常数就降到了4。

不过这个题还有一个问题，就是我们的f[u]里面有乘积式，也就意味着，我们在更改重链头的时候它的父亲需要除以重链头的f+1。虽然\texttt{FWT}是可以除的，但是如果里面有0的话就无法让信息复原。一个解决办法是再开一个线段树维护每个节点所有虚儿子的f+1之积，另外一种方法就是记录0的个数。我用的前者，因为比较好封装。

于是，我们就在\Theta(nm+q\log^2nm)的时间复杂度内解决了这个问题。

不过话说，luogu上有人出了可以卡掉树剖的数据，所以会\texttt{T}掉两个点，以下代码只能在\texttt{LOJ}通过。

这里提一个小醒，\texttt{FWT}数组每次初始化的时候不能\texttt{memset}，否则会\texttt{MLE}。

\texttt{Code}

代码戳这里打开