求调5个点mle,悬赏一关注
查看原帖
求调5个点mle,悬赏一关注
500596
Wtbjp楼主2023/2/19 11:09
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node{
	int l,r,sum,lazy;
}a[N*4];
int n,q;
int dep[N],siz[N],son[N],tot,id[N],fat[N],tp[N];
vector<int>s[N];
inline void down(int x){
	a[x*2].lazy+=a[x].lazy;
	a[x*2+1].lazy+=a[x].lazy;
	a[x*2].sum+=(a[x*2].r-a[x*2].l+1)*a[x].lazy;
	a[x*2+1].sum+=(a[x*2+1].r-a[x*2+1].l+1)*a[x].lazy;
	a[x].lazy=0;
}
void jia(int l,int r,int x,int s){
	if(a[x].l>=l&&a[x].r<=r){
		a[x].lazy+=s;
		a[x].sum+=(a[x].r-a[x].l+1)*s;
		return;
	}
	down(x);
	int mid=(a[x].l+a[x].r)/2;
	if(mid>=l)jia(l,r,x*2,s);
	if(mid<r)jia(l,r,x*2+1,s);
	a[x].sum=a[x*2].sum+a[x*2+1].sum;
}
int cha(int l,int r,int x){
	if(a[x].l>=l&&a[x].r<=r){
		return a[x].sum;
	}
	down(x);
	int ret=0,mid=(a[x].l+a[x].r)/2;
	if(mid>=l)ret+=cha(l,r,x*2);
	if(mid<r)ret+=cha(l,r,x*2+1);
	return ret;
}
void js(int l,int r,int x){
	a[x].l=l,a[x].r=r;
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	js(l,mid,x*2);
	js(mid+1,r,x*2+1);
}
void dfs(int x,int fa){
	siz[x]=1;
	int maxx=0;
	for(int y:s[x]){
		if(y==fa)continue;
		dep[y]=dep[x]+1;
		fat[y]=x;
		dfs(y,x);
		siz[x]+=siz[y];
		if(siz[y]>maxx){
			maxx=siz[y];
			son[x]=y;
		}
	}
}
void dfs1(int x,int fa,int t){
	tp[x]=t;
	id[x]=tot++;
	if(!son[x])return;
	dfs1(son[x],x,t);
	for(int y:s[x]){
		if(y==son[x]||y==fa)continue;
		dfs1(y,y,x);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		s[x].push_back(y);
		s[y].push_back(x);
	}
	dep[0]=1;
	dfs(0,0);
	dfs1(0,0,0);
	js(0,n-1,1);
	cin>>q;
	while(q--){
		char ch;
		int x,y,z,ans=0;
		cin>>ch;
		if(ch=='A'){
			cin>>x>>y>>z;
			while(tp[x]!=tp[y]){
				if(dep[tp[x]]<dep[tp[y]])swap(x,y);
				jia(id[tp[x]],id[x],1,z);
				x=fat[tp[x]];
			}
			if(dep[x]<dep[y])swap(x,y);
			jia(id[y],id[x],1,z);
		}
		else{
			cin>>x;
			cout<<cha(id[x],id[x]+siz[x]-1,1)<<"\n";
		}
	}
	return 0;
}
2023/2/19 11:09
加载中...