[SDOI2017]切树游戏 题解
由于不会所谓全局平衡二叉树的做法，所以 Luogu 上 T 飞了，只有 80pts ，但是 LOJ 可过
学习自： SDOI2017切树游戏 - Men always remember love because of romance only. 这里想用自己的理解讲一遍，加深理解
Statement
SDOI2017 切树游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Solution
容易设 \(dp_{u,k}\) 表示 \(u\) 为最高点，价值为 \(k\) 的联通块的个数，假设我们已经统计了前 \(x\) 个儿子的贡献，现在正在加入儿子 \(v\) ，那么
\[dp_{u,k}=\sum_{i\oplus j=k}dp_{u,i}dp_{v,j}+dp_{u,k} \]这样对于询问 \(k\) ，答案就是 \(\sum dp_{u,k}\)
容易发现如果我们每次询问都重新计算的话，复杂度 \(O(qnm^2)\)
考虑加一个 FWT 优化那个异或卷积，\(O(qnm\log m)\) 依然不行
显然我们没有必要每一次都把所有的重新算一遍，
涉及到修改操作，考虑动态 DP，先树剖一遍
动态 DP 的思想是在初始状态求出 \(u\) 轻儿子部分的信息，然后再修改一个点 \(u\) 的时候，利用已知的轻儿子的信息，我们容易算出新的 dp 值。
因为他所在的重链上所有点的轻儿子的信息都知道了，所以我们还可以从底向上递推得到重链上每一个的新 dp 值
发现我们只关心当前点所在重链的链顶的新的 DP 值是多少（为了更新 fa[top[u]] 的轻儿子的信息）
然后发现这个递推的过程我们可以通过线段树矩阵乘法加速，修改 \(u\) 时顺便修改一下他的矩阵即可
容易发现这样的过程，我们只需要利用矩阵计算重链顶部(top[x])的新 DP 值，以修改往上跳重链的时候所到的端点(fa[top[u]])的轻儿子信息即可
这些 \(fa[top[u]]\) 的个数显然是 \(O(log)\) 的，毕竟重链只有 log 条，这样保证了复杂度
所以我们现在考虑构造一下这个从重儿子转移到当前点的转移矩阵满足它仅和当前点轻儿子信息有关
设 \(val_u=FWT(a_u)\) ，即 \(dp_u\) 的初始化是 \(dp_{u,a_u}=1\) ，\(val_u\) 加上了一个 FWT
设 \(f_u=val_u\prod (f_v+1)\) ，即 \(dp\) 数组
设 \(g_u=f_u+\sum g_v\) ，即 \(u\) 子树内的答案（全局答案 \(\sum f_u\) 嘛）
设 \(lf_u=val_u\prod\limits_{v\in lightson_u}(f_v+1)\) ，即 \(u\) 除掉重儿子的贡献
设 \(lg_u=\sum\limits_{v\in lightson_u}g_v\) ，即 \(u\) 轻儿子答案
设 \(w\) 表示 \(u\) 的重儿子
容易发现：（由定义可知嘛）
\[f_u=lf_u(val_w+1)\\ g_u=f_u+lg_u+g_w\\ \]继续展开一下：
\[f_u=lf_uval_w+lf_u\\ g_u=lf_uval_w+lf_u+lg_u+g_w \]回想我们的目的是 构造一下这个从重儿子转移到当前点的转移矩阵满足它仅和当前点轻儿子信息有关
（可能有一点绕，
可以推出：
\[\begin{bmatrix} lf_u&0&lf_u\\lf_u&1&lf_u+lg_u\\0&0&1 \end{bmatrix} \begin{bmatrix}f_w\\g_w\\1 \end{bmatrix}= \begin{bmatrix} f_u\\g_u\\1 \end{bmatrix} \]至此，我们好像是做完了，考虑到常数可能有点大，嫖一个性质：
\[\begin{bmatrix} a&0&b\\c&1&d\\0&0&1 \end{bmatrix} \begin{bmatrix} A&0&B\\C&1&D\\0&0&1 \end{bmatrix}= \begin{bmatrix} aA&0&aB+b\\Ac+C&1&cB+d+D\\0&0&1 \end{bmatrix} \]所以我们的矩阵只需要维护 4 个值即可。
不幸的是，我们的 \(f_u\) 中出现了乘积式，所以，当我们需要重算 fa[top[u]] 的 lf 的值的时候，是需要先除掉旧 \(f_{top[u]}\) 的，由于可能会出现 \(0\) ，这样信息就还原不了
这里的解决方式是，开一个线段树，记录轻儿子的 \(f\) 值，算 \(fa[top[u]]\) 新 \(lf\) 的时候，线段树算一下即可。
Code
代码调傻了，所以导致最后和巨佬 Walking_Dead 的代码几乎“融为一体” qwq
#include
using namespace std;
const int N = 3e4+5;
const int M = 150;
const int mod = 10007;
//char buf[1<<23],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
void write(int x){
if(x<0)x=-x,putchar('-');
if(x>9)write(x/10);
putchar(x%10+'0');
}
int ksm(int a,int b){
int res=1;
for(;b;a=a*a%mod,b>>=1)
if(b&1)res=res*a%mod;
return res;
}
int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
int dec(int a,int b){return a>=b?a-b:a+mod-b;}
int mul(int a,int b){return a*b%mod;}
int n,m,q,inv2,x,y;
char op[5];
struct Fwt{
int f[M];
int& operator [](int key){return f[key];}
void clear(){for(int i=0;i
struct Segment_Tree{
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
int len,L,R;
Type t[N<<2],ori[N],cge;
void pushup(int rt){t[rt]=t[ls]*t[rs];}
void build(int l,int r,int rt){
if(l==r)return t[rt]=ori[l],void();
build(l,mid,ls),build(mid+1,r,rs);
pushup(rt);
}
void change(int l,int r,int rt,int id){
if(l==r)return t[rt]=cge,void();
id<=mid?change(l,mid,ls,id):change(mid+1,r,rs,id);
pushup(rt);
}
Type query(int l,int r,int rt){
if(L<=l&&r<=R)return t[rt];
if(R<=mid)return query(l,mid,ls);
if(midTree1;
Segment_TreeTree2;
vectorEdge[N];
void fwt(int *f,int op){
for(int i=2;i<=m;i<<=1)
for(int j=0,p=i>>1;ja[a[u].son].siz&&(a[u].son=v,1));
}
void dfs2(int u,int top){
a[u].top=top,a[u].val[a[u].w]=1,fwt(a[u].val.f,1),a[u].lf=a[u].val,a[u].id1=++Tree1.len;
if(!a[u].son)return a[u].ed=u,a[u].f=a[u].g=a[u].lf,void();
dfs2(a[u].son,top);
for(auto v:Edge[u])if(v!=a[u].fa&&v!=a[u].son)
dfs2(v,v),a[u].lf=a[u].lf+a[u].lf*a[v].f,a[u].lg=a[u].lg+a[v].g;
int v=a[u].son;
a[u].ed=a[v].ed,a[u].f=a[u].lf*a[v].f+a[u].lf,a[u].g=a[u].f+a[u].lg+a[v].g,a[u].l=Tree2.len+1;
for(auto v:Edge[u])if(v!=a[u].fa&&v!=a[u].son)a[v].id2=++Tree2.len;
a[u].r=Tree2.len;
}
void change(int u,int v){
a[u].val.clear(),a[u].val[v]=1,fwt(a[u].val.f,1);
Tree2.L=a[u].l,Tree2.R=a[u].r;
if(1<=a[u].l&&a[u].l<=a[u].r)a[u].lf=a[u].val*Tree2.query(1,Tree2.len,1);
else a[u].lf=a[u].val;
Matrix S;
while(1){
Tree1.cge=(Matrix){a[u].lf,a[u].lf,a[u].lf,a[u].lf+a[u].lg};
Tree1.change(1,Tree1.len,1,a[u].id1);
Tree1.L=a[u=a[u].top].id1,Tree1.R=a[a[u].ed].id1;
S=Tree1.query(1,Tree1.len,1);
if(u==1)break;
a[a[u].fa].lg=a[a[u].fa].lg-a[u].g+S.d,a[u].g=S.d;
Tree2.cge=S.b+one,Tree2.change(1,Tree2.len,1,a[u].id2);
Tree2.L=a[a[u].fa].l,Tree2.R=a[a[u].fa].r;
a[a[u].fa].lf=a[a[u].fa].val*Tree2.query(1,Tree2.len,1);
u=a[u].fa;
}
ans=S.d,fwt(ans.f,-1);
}
signed main(){
n=read(),m=read(),inv2=ksm(2,mod-2);
for(int i=0;i