OI - 切树游戏(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 切树游戏(LOJ)

发表于 更新于 分类于 Valine：

尽可能卡常还是卡不过洛谷的评测机……只过了 LOJ 的评测 awa

# 题面

点击展开/折叠题面

现在小Q有一棵 $n$ 个结点的无根树 $T$，结点依次编号为 $1$ 到 $n$，其中结点 $i$ 的权值为 $v_i$​。

定义一棵树的价值为它所有点的权值的异或和，一棵树 $T$ 的连通子树就是它的一个连通子图，并且这个图也是一棵树。

小Q想要在这棵树上玩切树游戏，他会不断做以下两种操作：

  1. `Change x y` 将编号为 $x$ 的结点的权值修改为 $y$。
  2. `Query k` 询问有多少棵 $T$ 的非空连通子树，满足其价值恰好为 $k$。

# 解析

首先如果你能够看出来这是个动态DP，大概就会按照下面的思路来做这道题：

如果没有修改，那么可以做一个 DP：$F_{u,i}$ 表示点 u 为根的子树中，所选点集包含 u，点集权值的异或和为 i 的方案数；又因为要统计整棵树的，所以定义 $G_{u,i}$ 表示 u 的子树中点集权值异或和为 i 的方案数。

于是有以下转移：

显然是一个异或卷积的事，记 $F_u,G_u$ 分别是 $F_{u,i},G_{u,i}$ 的普通生成函数，定义生成函数的乘法是异或卷积。则有：

这个东西就可以用 FWT 迅速地完成。

然后我们考虑动态DP，因为是在树上，我们就分轻重儿子考虑——$g_u,f_u$ 的定义式如下（$lson_u$ 指 u 的轻儿子）：

因此可以写出 $F_u,G_u$ 关于其重儿子 $wei_u$ 的转移式：

按照套路，接下来应该是矩阵环节了，只不过这个矩阵的元素是多项式，乘法和加法分别是异或卷积和多项式加法。

看起来这个转移矩阵是 $3\times3$ 的，乘法有 27 的常数……能否砍掉一些运算？

考虑转移过程中两个矩阵相乘：

于是只需要储存 4 个值，即上面的 $A_0,A_1,A_2,A_3$。省去不少常数。

最后，我们建出全局平衡二叉树，查询只需要计算（$M$ 是二叉树的根统计到的转移矩阵的积）：

而修改 u 的权为 key 的操作时，首先修改 $f_{u}$（因为 $x^{val_u}$ 改变了）并更新矩阵，在重链的交接处（轻儿子），修改父亲的 $f,g$。

修改 $g$ 很简单，假如父节点 $u$ 的轻儿子 $v$ 的DP值改变了，则 $g_u$ 先减去原来的 $G_v$，再加上改变后的 $G_v$；修改 $f$ 也同理，先把 $f_u$ 除以原来的 $F_v$，再乘上新的 $F_v$……

等等，这玩意可以除法？由于 $F_v$ 完全可能有系数 0，这样是没有逆元的。（网上有一种记录 0 的个数的做法，的确巧妙，但是我还是写了无脑的线段树 awa）那么我们可以暴力地用线段树维护每个节点的子节点的 $F_v$ 的卷积。

具体地说，对于 $u$，对它所有的子节点的 $F_v$ 做单点修改、根节点求卷积。这样就比较无脑，只是注意一下线段树的标号。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3e4+10,MOD=10007,M=130;

#define cs const int &
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}
inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
inline char Rc(){
	register int c=getchar();
	while(c!='Q' && c!='C') c=getchar();
	return (char)c;
}

const int INV2=Pow(2,MOD-2);

struct GRAPH{
	int head[N],nxt[N<<1],to[N<<1],ncnt;
	void AddEdge(int u,int v){
		int p=++ncnt,q=++ncnt;
		nxt[p]=head[u],to[p]=v,head[u]=p;
		nxt[q]=head[v],to[q]=u,head[v]=q;
	}
	int operator [](const int &u){return head[u];}
}Gr;

int n,m;
int val[N],tmpt[N],sid[N],ns[N];

struct ARRAY{
	int ary[M];
	void FWT(int len,int typ){
		for(int l=2,t=1;l<=len;l<<=1,t<<=1)
			for(int i=0;i<len;i+=l)
				for(int j=i;j<i+t;j++){
					int Aj=ary[j];
					ary[j]=Add(Aj,ary[j+t]),ary[j+t]=Sub(Aj,ary[j+t]);
					if(typ==-1) ary[j]=Mul(ary[j],INV2),ary[j+t]=Mul(ary[j+t],INV2);
				}
	}
	int& operator [](const int &i){return ary[i];}
	friend ARRAY operator *(ARRAY A,ARRAY B){
		for(int i=0;i<m;i++) A[i]=Mul(A[i],B[i]);
		return A;
	}
	friend ARRAY operator +(ARRAY A,ARRAY B){
		for(int i=0;i<m;i++) A[i]=Add(A[i],B[i]);
		return A;
	}
	friend ARRAY operator -(ARRAY A,ARRAY B){
		for(int i=0;i<m;i++) A[i]=Sub(A[i],B[i]);
		return A;
	}
	void Clean(int siz){for(int i=0;i<siz;i++)ary[i]=0;}
	void Debug(){
		printf("{ ");
		FWT(m,-1);
		for(int i=0;i<m;i++) printf("%d ",ary[i]);
		FWT(m,1);
		printf("}\n");
	}
}F[N],f[N],G[N],g[N],One,cop;

int spp;

struct SEGTREE{
	int nxt[N*4][2],head[N],ncnt;
	ARRAY num[N*4];
	void PushUp(int u){num[u]=num[nxt[u][0]]*num[nxt[u][1]];}
	void Build(int &u,int le,int ri){
		u=++ncnt;
		if(le==ri){
			if(le!=spp) num[u]=F[tmpt[le]]+One;
			else num[u]=cop;
			return;
		}
		int mi=(le+ri)>>1;
		Build(nxt[u][0],le,mi),Build(nxt[u][1],mi+1,ri);
		PushUp(u);
	}
	void Modify(int u,int le,int ri,int po){
		if(le==ri){
			num[u]=cop;
			return;
		}
		int mi=(le+ri)>>1;
		if(po<=mi) Modify(nxt[u][0],le,mi,po);
		else Modify(nxt[u][1],mi+1,ri,po);
		PushUp(u);
	}
	int& operator [](const int &u){return head[u];}
}Se;

struct MATRIX{
	ARRAY mt00,mt02,mt10,mt12;
	MATRIX(){}
	MATRIX(ARRAY m00,ARRAY m02,ARRAY m10,ARRAY m12):mt00(m00),mt02(m02),mt10(m10),mt12(m12){}
	inline friend MATRIX operator *(const MATRIX &A,const MATRIX &B){
		return MATRIX(A.mt00*B.mt00,A.mt00*B.mt02+A.mt02,A.mt10*B.mt00+B.mt10,B.mt12+A.mt12+A.mt10*B.mt02);
	}
};

namespace BST{
	int siz[N],lsiz[N],wei[N],pnts[N],fa[N],ch[N][2],tp[N];
	bool vis[N];
	MATRIX pmt[N],mt[N];
	void DFS(cs u,cs fa){
		siz[u]=1;
		F[u][val[u]]=1,F[u].FWT(m,1);
		for(int it=Gr[u];it;it=Gr.nxt[it]){
			int v=Gr.to[it];
			if(v==fa) continue;
			DFS(v,u);
			siz[u]+=siz[v];
			if(siz[wei[u]]<siz[v]) wei[u]=v;
			F[u]=F[u]*(F[v]+One);
			G[u]=G[u]+G[v];
		}
		lsiz[u]=siz[u]-siz[wei[u]];
		G[u]=G[u]+F[u];
	}
	void DFS2(cs u,cs fa){
		if(wei[u]) DFS2(wei[u],u);
		f[u][val[u]]=1,f[u].FWT(m,1);
		for(int it=Gr[u];it;it=Gr.nxt[it]){
			int v=Gr.to[it];
			if(v==fa || v==wei[u]) continue;
			DFS2(v,u);
			f[u]=f[u]*(F[v]+One);
			g[u]=g[u]+G[v];
		}
		for(int it=Gr[u];it;it=Gr.nxt[it]){
			int v=Gr.to[it];
			if(v==fa || v==wei[u]) continue;
			tmpt[sid[v]=++ns[u]]=v;
		}
		spp=++ns[u];
		cop.Clean(m),cop[val[u]]=1,cop.FWT(m,1);
		Se.Build(Se[u],1,ns[u]);
	}
	inline void PushUp(cs u){
		mt[u]=pmt[u];
		if(ch[u][0]) mt[u]=mt[ch[u][0]]*mt[u];
		if(ch[u][1]) mt[u]=mt[u]*mt[ch[u][1]];
	}
	inline void SetUp(cs u){
		pmt[u].mt00=pmt[u].mt02=pmt[u].mt10=f[u];
		pmt[u].mt12=f[u]+g[u];
	}
	inline int EBuild(cs le,cs ri){
		if(le>ri) return 0;
		int tot=0;
		for(register int i=le;i<=ri;i++) tot+=lsiz[pnts[i]];
		for(register int i=le,ntot=lsiz[pnts[i]];i<=ri;ntot+=lsiz[pnts[++i]])
			if(ntot*2>=tot){
				int lc=EBuild(le,i-1),rc=EBuild(i+1,ri),u=pnts[i];
				ch[u][0]=lc,ch[u][1]=rc;
				if(lc) fa[lc]=u;
				if(rc) fa[rc]=u;
				SetUp(u),PushUp(u);
				return u;
			}
		return 0;
	}
	inline int Build(int u){
		for(register int pu=u;pu;pu=wei[pu]) vis[pu]=true,tp[pu]=u;
		for(register int pu=u;pu;pu=wei[pu])
			for(register int it=Gr[pu];it;it=Gr.nxt[it])
				if(!vis[Gr.to[it]])
					fa[Build(Gr.to[it])]=pu;
		int npnt=0;
		for(register int pu=u;pu;pu=wei[pu]) pnts[++npnt]=pu;
		return EBuild(1,npnt);
	}
	bool Root(cs u){return !fa[u] || (ch[fa[u]][0]!=u && ch[fa[u]][1]!=u);}
	void Modify(register int u,cs key){
		cop.Clean(m),cop[key]=1,cop.FWT(m,1);
		Se.Modify(Se[u],1,ns[u],ns[u]);
		f[u]=Se.num[Se[u]];
		SetUp(u);
		while(u){
			if(fa[u] && Root(u)){
				//! 当前 u 的值实际上是 top[u]
				g[fa[u]]=g[fa[u]]-mt[u].mt12;
				PushUp(u);
				g[fa[u]]=g[fa[u]]+mt[u].mt12;
				cop=mt[u].mt02+One;
				// cop.Debug();
				Se.Modify(Se[fa[u]],1,ns[fa[u]],sid[tp[u]]);
				f[fa[u]]=Se.num[Se[fa[u]]];
				// printf("[%d]:",fa[u]);f[fa[u]].Debug();
				SetUp(fa[u]);
			}
			else PushUp(u);
			u=fa[u];
		}
	}
}
int rt;
int Solve(int key){
	cop=BST::mt[rt].mt12;cop.FWT(m,-1);
	return cop[key];
}

int main(){
	/*Input*/
	n=Ri(),m=Ri();
	int tm=1;
	while(tm<m) tm<<=1;
	m=tm;
	for(int i=1;i<=n;i++) val[i]=Ri();
	for(int i=1;i<n;i++) Gr.AddEdge(Ri(),Ri());
	/*Prepare*/
	One[0]=1,One.FWT(m,1);
	/*Build*/
	BST::DFS(1,0);BST::DFS2(1,0);
	rt=BST::Build(1);
	/*Query*/
	for(int cas=Ri();cas;cas--){
		char cmd=Rc();
		if(cmd=='C'){
			int u=Ri(),key=Ri();
			BST::Modify(u,key);
		}
		else printf("%d\n",Solve(Ri()));
	}
	return 0;
}

THE END

Thanks for reading!

> Linked 年岁易偷-网易云