自动搬运

查看原文

来自洛谷，原作者为

	LHF qwq

搬运于2025-08-24 22:32:23，当前版本为作者最后更新于2022-09-27 21:09:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

讲一种代码十分简短的做法（1.34k，目前(2022.9.17)是最短解）。

首先可以把子树操作变成 DFS 序上的操作，考虑对序列进行分块，设块的大小为 $B1$，对于散块，我们可以通过暴力维护，而对于整块，我们另外考虑方法。

我们发现整块直接维护比较困难，但考虑到有 $\bmod x=y$，这显然就是根号分治嘛，再设阈值 $B2$，当 $x\le B2$ 的时候考虑直接在对应的块上面暴力打标记，考虑 $x>B2$ 的时候怎么做。

我们考虑深度为 $i$ 并且在第 $j$ 个块的点的标记数组，显然当 $x>B2$ 的时候我们可以直接暴力在对应深度上打标记，由于一横行只有 $n/B1$ 个元素，所以我们可以先差分，查询的时候直接暴力查即可。

总复杂度 $O(\frac{nq}{B1}+\frac{nq}{B2}+q(B1+B2))$，正常来说是 $B1=B2=\sqrt n$ 时比较优，但这样空间就是 $2n^{1.5}$ 了，过不去，所以需要调整一下，我把 $B1$ 调到了 $1500$，$B2$ 调到了 $200$ 就过了。

下面是代码（没加快读没卡常能过）

#include<cstdio>
#include<cmath>
using namespace std;
const int N=3e5+2,M=202;
int dep[N],dfn[N],cnt,id[N],s[N],B,B1;
struct edge{
	int next,to;
}e[N];
int first[N],len,T,n,siz[N],ans;
int t1[N][M],t2[M][M][M];
void add(int a,int b)
{
	e[++len]=edge{first[a],b};
	first[a]=len;
}
void BF(int l,int r,int x,int y,int z)
{
	for(int i=l;i<=r;i++)
		if(dep[i]%x==y) s[i]+=z;
}
void modify(int l,int r,int x,int y,int z)
{
	y%=x;
	if(id[l]==id[r]) BF(l,r,x,y,z);
	else
	{
		BF(l,id[l]*B,x,y,z);
		BF((id[r]-1)*B+1,r,x,y,z);
		if(x<=B1)
			for(int i=id[l]+1;i<id[r];i++)
				t2[i][x][y]+=z;
		else
			for(int i=y;i<=n;i+=x)
				t1[i][id[l]+1]+=z,t1[i][id[r]]-=z;
	}
}
void dfs(int x)
{
	siz[x]=1;
	for(int i=first[x],y;i;i=e[i].next)
		dep[dfn[y=e[i].to]=++cnt]=dep[dfn[x]]+1,dfs(y),siz[x]+=siz[y];
}
int a,x,y,z,op;
int main()
{
	scanf("%d%d",&n,&T);
	for(int i=2;i<=n;i++) scanf("%d",&x),add(x,i);
	dfn[cnt=1]=1,dfs(1);
	B=1500,B1=200;
	for(int i=1;i<=n;i++) id[i]=(i-1)/B+1;
	while(T--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d%d%d",&a,&x,&y,&z);
			modify(dfn[a],dfn[a]+siz[a]-1,x,dep[dfn[a]]+y,z);
		}
		else
		{
			scanf("%d",&x);
			ans=s[x=dfn[x]];
			for(int i=1;i<=id[x];i++)
				ans+=t1[dep[x]][i];
			for(int i=1;i<=B1;i++)
				ans+=t2[id[x]][i][dep[x]%i];
			printf("%d\n",ans);
		}
	}
}