MnZn 树剖WA50 求调
查看原帖
MnZn 树剖WA50 求调
361141
_JF_殉情楼主2024/4/14 09:16
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
#define int long long 
struct node{
	int sum=0,lzy=0;
}d[N];
int n,dfn[N],lst[N],fa[N],siz[N],dep[N],hvs[N],top[N],tot;
vector<int> g[N];
void dfs(int u,int fath){
	fa[u]=fath,siz[u]=1,dep[u]=dep[fath]+1,hvs[u]=-1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fath)	continue;
		dfs(v,u),siz[u]+=siz[v];
		if(hvs[u]==-1||siz[v]>siz[hvs[u]])	hvs[u]=v;
	}
}
void rdfs(int u,int fath,int T){
	dfn[u]=++tot,lst[u]=tot,top[u]=T;
	if(hvs[u]==-1)	return ;
	rdfs(hvs[u],u,T);
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		lst[u]=max(lst[u],lst[v]);
		if(v==fath||v==hvs[u])	continue;
		rdfs(v,u,v);
	}
}
void push_down(int s,int mid,int t,int p){
	d[p<<1].sum+=(mid-s+1)*d[p].lzy,d[p<<1|1].sum+=(t-mid)*d[p].lzy;
	d[p<<1].lzy+=d[p].lzy,d[p<<1|1].lzy+=d[p].lzy;
	d[p].lzy=0;
}
void update(int l,int r,int s,int t,int p,int change){
	if(l<=s&&t<=r){d[p].sum+=(t-s+1)*change,d[p].lzy+=change;return ;}
	int mid=(s+t)>>1;
	push_down(s,mid,t,p);
	if(l<=mid)	update(l,r,s,mid,p<<1,change);
	if(r>mid)	update(l,r,mid+1,t,p<<1|1,change);
	d[p].sum=d[p<<1].sum+d[p<<1|1].sum;
}
int Query(int l,int r,int s,int t,int p){
	if(l<=s&&t<=r)	return d[p].sum;
	int mid=(s+t)>>1,ans=0;
	push_down(s,mid,t,p);
	if(l<=mid)	ans+=Query(l,r,s,mid,p<<1);
	if(r>mid)	ans+=Query(l,r,mid+1,t,p<<1|1);
	return ans;
}
void jump(int x,int y,int change){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])	swap(x,y);
		update(dfn[top[x]],dfn[x],1,n,1,change),x=fa[top[x]];
	}
	if(dep[x]<dep[y])	swap(x,y);
	update(dfn[y],dfn[x],1,n,1,change);		
}
signed main()
{
	cin>>n;
	for(int i=1,u,v;i<n;i++)	cin>>u>>v,g[u+1].push_back(v+1),g[v+1].push_back(u+1);
	dfs(1,0),rdfs(1,0,1); 
	int q;
	cin>>q;
	while(q--){
		char c;
		cin>>c;
		int x,y,change;
		if(c=='A')	cin>>x>>y>>change,x++,y++,jump(x,y,change);
		else	cin>>x,x++,cout<<Query(dfn[x],lst[x],1,n,1)<<endl;
	}
	return 0;
}
2024/4/14 09:16
加载中...