[CF1076E]Vasya and a Tree（树上差分）
Guxuer
编辑于 2021年09月04日 14:11
收录于文集
共17篇

题意：一棵树有n个节点，1号点为根，初始时所有点点权为0。进行m次操作，每次操作选以x为根的子树，其中与x距离<=y的全部+z。

规模：n,m<=300000。

分析：因为要将一个子树进行加减，同时只有修改没有查询，所以考虑树上差分，每次操作将ans[x]+=z。同时因为距离<=y的才加，所以将距离为y+1的点 i 全部ans[i]-=z。但是这样的点 i 可能有n个，时间复杂度又变成了n^2，所以考虑将所有深度相同的点存到同一个vector中，这样它们的下标是连续的，可以进行区间修改。同时又因为只有修改没有查询，所以再次运用差分（当然区间修改像zqs2020和kzsn巨佬用树状数组或者像Aurora神犇用线段树做都是可以的）。修改距离为y+1的点，也就是在深度为h[x]+y+1的vector数组中查找在x的子树中的点，可以记录下每个点的dfs序，这样就可以在对应深度的vector数组中二分查找第一个in [i]>=in [x]的点 i，c[ i ]-=z；再二分查找第一个ot [j]>ot [x]的点 j，c[ j ]+=z。最后先枚举每个深度的vector数组，用前缀和将差分的c数组回收，然后再把c数组的值加到ans数组上，然后dfs树上前缀和，儿子节点加上父亲节点的ans值即可。

代码（只有1500B。如果用树状数组2000B左右，线段树2500B左右）

代码块
C++
自动换行
复制代码
#include<bits/stdc++.h>
using namespace std;
int n,m,lst[300003],cntl,h[300003],in[300003],ot[300003],cntt,maxh;
long long ans[300003],c[300003];
struct edge{int nxt,toward;}line[600006];
void add(int x,int y)
{
	line[++cntl].nxt=lst[x];
	lst[x]=cntl;
	line[cntl].toward=y;
	return;
}
vector<int>a[300003];
void dfs(int x,int fa)
{
	in[x]=++cntt;h[x]=h[fa]+1;
	maxh=max(maxh,h[x]);
	a[h[x]].push_back(x);
	for(int i=lst[x];i;i=line[i].nxt)
		if(line[i].toward!=fa)
			dfs(line[i].toward,x);
	ot[x]=cntt;
	return;
}
bool cmpo(int x,int y){return ot[x]<ot[y];}
bool cmpi(int x,int y){return in[x]<in[y];}
void dfss(int x,int fa)
{
	ans[x]+=ans[fa]+c[x];
	for(int i=lst[x];i;i=line[i].nxt)
		if(line[i].toward!=fa)
			dfss(line[i].toward,x);
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
	dfs(1,0);
	scanf("%d",&m);
	vector<int>::iterator st,ed;
	for(int i=1,x,y,z;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ans[x]+=z;
		int hh=min(maxh+1,h[x]+y+1);
		if(hh!=maxh+1)
		{
			ed=upper_bound(a[hh].begin(),a[hh].end(),x,cmpo);
			st=lower_bound(a[hh].begin(),a[hh].end(),x,cmpi);
			if(ed>st)
			{
				c[*st]-=z;
				if(ed!=a[hh].end()) c[*ed]+=z;
			}
		}
	}
	for(int i=1;i<=maxh;i++)
		for(st=a[i].begin(),ed=++st,st--;ed!=a[i].end();st++,ed++)
			c[*ed]+=c[*st];
	dfss(1,0);
	for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
	return 0;
}
复制成功

本文为我原创，未经授权禁止转载
cv12227969