多校联测12 树

题目大意

有一棵有$n$个点且以$1$为根的树，有$q$次操作，操作分为两种类型：

• 将点$v$子树内与它距离模$x$等于$y$的所有点的权值加上$z$
• 询问点$v$的权值

$1\le n,q\le 3\times 10^5,1\le z\le 1000$

时间限制$6000ms$，空间限制$256MB$。

题解

前置知识：根号分治

设点$i$在树上的深度为$de{p}_i$，则第一类操作可以看成将$v$的子树内所有满足$de{p}_i\%x=(de{p}_v+y)\%p$的点$i$的权值加上$z$。

我们可以求每个点在树上的$dfs$序，那么在一个子树内的节点在$dfs$序上是一段连续的区间，这样操作一就变成区间修改了。

我们可以用分块来维护$dfs$序上每个点的权值。

我们考虑根据$x$的大小来进行根号分治。在操作二时，将两个部分的答案加在一起即可得到答案。

当$x\le \sqrt{n}$时，设$m{d}_{i,j,k}$为第$i$块中深度模$j$为$k$的点需要整体加的值，对于操作一（也就是一次区间修改），分为整块和散块处理，是$O(\sqrt{n})$的。而操作二要对每一个小于等于$\sqrt{n}$的模数$j$都要$O(1)$查询，所以也是$O(\sqrt{n})$的。那么，这部分的时间复杂度为$O(q\sqrt{n})$。

当$x>\sqrt{n}$时，设$d{s}_{i,j}$表示深度为$i$时第$j$块上要加的值。也是分为整块和散块来处理。对于整块，枚举每个满足题意的深度。如果将每个深度的每一块都修改的话，一次操作一是$O(n)$的，所以我们可以维护这些块的拆分，那么对每一种深度都可以$O(1)$修改，是$O(\sqrt{n})$的。对于操作二，在$v$的深度对应的块中求对应段的$d{s}_{i,j}$之和即可，直接枚举并求和，也是$O(\sqrt{n})$的。那么，这部分的时间复杂度为$O(q\sqrt{n})$。

总时间复杂度为$O(q\sqrt{n})$，空间复杂度为$O(n\sqrt{n})$，这是按块数和块长为$\sqrt{n}$来得到的。如果$MLE$，可以适当改变块数和块长。

code

#include
using namespace std;
const int N=300000,B=200,K=1500;
int n,Q,bl,ct=0,tot=0,d[2*N+5],l[2*N+5],r[2*N+5],dfn[N+5],s[N+5],dep[N+5],siz[N+5];
int mx,ans,hv[N+5],ds[N+5][B+5],md[K+5][B+5][B+5];
void add(int xx,int yy){
	l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
int pos(int i){
	return (i-1)/bl+1;
}
void dfs(int u,int fa){
	dfn[u]=++ct;
	s[ct]=u;
	siz[u]=1;
	dep[u]=dep[fa]+1;
	mx=max(mx,dep[u]);
	for(int i=r[u];i;i=l[i]){
		if(d[i]==fa) continue;
		dfs(d[i],u);
		siz[u]+=siz[d[i]];
	}
}
void pt(int dd,int l,int r,int x,int y,int z){
	int vl=pos(l),vr=pos(r);
	if(vl==vr){
		for(int i=l;i<=r;i++){
			if(dep[s[i]]%x==y) hv[i]+=z;
		}
		return;
	}
	for(int i=l;i<=vl*bl;i++){
		if(dep[s[i]]%x==y) hv[i]+=z;
	}
	for(int i=vr*bl-bl+1;i<=r;i++){
		if(dep[s[i]]%x==y) hv[i]+=z;
	}
	if(x<=B){
		for(int i=vl+1;i<=vr-1;i++) md[i][x][y]+=z;
	}
	else{
		for(int i=dd;i<=mx;i+=x){
			ds[i][vl+1]+=z;ds[i][vr]-=z;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&Q);
	bl=n/B+1;
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=Q;i++){
		int tp,v,x,y,z;
		scanf("%d",&tp);
		if(tp==1){
			scanf("%d%d%d%d",&v,&x,&y,&z);
			pt(dep[v]+y,dfn[v],dfn[v]+siz[v]-1,x,(y+dep[v])%x,z);
		}
		else{
			scanf("%d",&v);
			ans=hv[dfn[v]];
			for(int i=1;i<=B;i++){
				ans+=md[pos(dfn[v])][i][dep[v]%i];
			}
			for(int i=1;i<=pos(dfn[v]);i++){
				ans+=ds[dep[v]][i];
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}
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