树剖模板全RE,玄关求助QWQ
查看原帖
树剖模板全RE,玄关求助QWQ
938212
OMG_NOIP楼主2024/3/28 19:46
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll>eg[1000005];
ll n,m,dep[1000005],fas[1000005],siz[1000005];
ll son[1000005],top[1000005],id[1000005],tot;
struct Point{
	ll L,R,sum,lz;
}po[1000005];
void build(ll p,ll x,ll y){
	po[p]={x,y,0,0};
	if(x==y)return;
	ll mid=(x+y)>>1;
	build(p<<1,1,mid);
	build(p<<1|1,mid+1,y);
}
void uplz(ll p,ll k){
	po[p].sum+=(po[p].R-po[p].L+1)*k;
	po[p].lz+=k;
}
void pushdown(ll p){
	if(po[p].lz!=0){
		uplz(p<<1,po[p].lz);
		uplz(p<<1|1,po[p].lz);
		po[p].lz=0;
	}
}
void modify(ll p,ll x,ll y,ll k){
	if(po[p].R<x|po[p].L>y)return;
	if(po[p].L>=x&&po[p].R<=y)return uplz(p,k);
	pushdown(p);
	modify(p<<1,x,y,k);
	modify(p<<1|1,x,y,k);
	po[p].sum=po[p<<1].sum+po[p<<1|1].sum;
}
ll query(ll p,ll x,ll y){
	if(po[p].R<x||po[p].L>y)return 0;
	if(po[p].L>=x&&po[p].R<=y)return po[p].sum;
	pushdown(p);
	return query(p<<1,x,y)+query(p<<1|1,x,y);
}
void dfs1(ll fa,ll p){
	dep[p]=dep[fa]+1;
	siz[p]=1;fas[p]=fa;
	for(ll v:eg[p]){
		if(v==fa)continue;
		dfs1(p,v);
		siz[p]+=siz[v];
		if(siz[v]>siz[son[p]])son[p]=v;
	}
}
void dfs2(ll p,ll tp){
	top[p]=tp;id[p]=++tot;
	if(!son[p])return;
	dfs2(son[p],tp);
	for(ll v:eg[p]){
		if(v==fas[p]||v==son[p])continue;
		dfs2(v,v);
	}
}
void modify_Tree(ll x,ll y,ll k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		modify(1,id[top[x]],id[x],k);
//		cout<<"L = "<<id[x]<<"   R = "<<id[y]<<endl;
		x=fas[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);;
	modify(1,id[x],id[y],k);
//	cout<<"L = "<<id[x]<<"   R = "<<id[y]<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(ll i=1;i<n;i++){
		ll x,y;cin>>x>>y;
		x++;y++;
		eg[x].push_back(y);
		eg[y].push_back(x);
	}
	dfs1(0,1);dfs2(1,1);
//	cout<<"dep : ";for(ll i=1;i<=n;i++)cout<<dep[i]<<" ";cout<<endl;
//	cout<<"siz : ";for(ll i=1;i<=n;i++)cout<<siz[i]<<" ";cout<<endl;
//	cout<<"fas : ";for(ll i=1;i<=n;i++)cout<<fas[i]<<" ";cout<<endl;
//	cout<<"top : ";for(ll i=1;i<=n;i++)cout<<top[i]<<" ";cout<<endl;
//	cout<<"son : ";for(ll i=1;i<=n;i++)cout<<son[i]<<" ";cout<<endl;
//	cout<<" id : ";for(ll i=1;i<=n;i++)cout<< id[i]<<" ";cout<<endl;
	build(1,1,n);
	cin>>m;
	while(m--){
		char op;cin>>op;
		ll x,y,k;cin>>x;x++;
		if(op=='A'){
			cin>>y>>k;y++;
//			cout<<"x = "<<x<<"   y = "<<y<<endl;
			modify_Tree(x,y,k);
		}
		else{
//			cout<<"x = "<<x<<endl;
			cout<<query(1,id[x],id[x]+siz[x]-1)<<endl;
		}
	}
	return 0;
}
2024/3/28 19:46
加载中...