TE+RLE求助 树剖+线段树
查看原帖
TE+RLE求助 树剖+线段树
288476
ll_dio楼主2022/8/23 21:18
#include<bits/stdc++.h>
#define N 100009
using namespace std;
typedef long long ll;
ll n,nE,hd[N],tI[N],tO[N],son[N],sz[N],top[N],timer,m,d[N],p[N];
struct Edge{
	ll t,nxt;
} es[2*N];
struct Segment{
	ll l,r,sum,len,toAdd;
} tr[4*N];
void add_edge(ll u,ll v){
	es[++nE]=(Edge){v,hd[u]};
	hd[u]=nE;
}
void dfs(ll u,ll fa){
	sz[u]=1; son[u]=0; d[u]=d[fa]+1;
	p[u]=fa;
	tI[u]=++timer;
	for(ll i=hd[u],v;i;i=es[i].nxt){
		v=es[i].t;
		if(v==fa) continue;
		dfs(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v]) son[u]=v;
	}
	tO[u]=timer;
}
void sfs(ll u,ll fa){
	if(son[fa]==u) top[u]=top[fa];
	else top[u]=u;
	for(ll i=hd[u],v;i;i=es[i].nxt){
		v=es[i].t;
		if(v==fa) continue;
		sfs(v,u);
	}
}
void build(ll u,ll l,ll r){
	tr[u]=(Segment){l,r,0,r-l+1,0};
	if(l==r) return;
	ll mid=(l+r)/2;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
}
void brush(ll u,ll delta){
	tr[u].sum+=tr[u].len*delta;
	tr[u].toAdd+=delta;
}
void pushdown(ll u){
	if(tr[u].l==tr[u].r) return;
	brush(2*u,tr[u].toAdd);
	brush(2*u+1,tr[u].toAdd);
	tr[u].toAdd=0;
}
void merge(ll u){
	if(tr[u].l==tr[u].r) return;
	tr[u].sum=tr[2*u].sum+tr[2*u+1].sum;
}
void add(ll u,ll l,ll r,ll delta){
	pushdown(u);
	if(tr[u].l>r||tr[u].r<l) return;
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].sum+=tr[u].len*delta;
		tr[u].toAdd+=delta;
	}
	add(2*u,l,r,delta);
	add(2*u+1,l,r,delta);
	merge(u);
}
ll query(ll u,ll l,ll r){
	pushdown(u);
	if(tr[u].l>r||tr[u].r<l) return 0;
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
	return query(2*u,l,r)+query(2*u+1,l,r);
}
void add_Tree(ll u,ll v,ll delta){
	while(top[u]!=top[v]){
		if(d[u]<d[v]) swap(u,v);
		add(1,tI[top[u]],tI[u],delta);
		u=p[top[u]];
	}
	if(tI[u]>tI[v]) swap(u,v);
	add(1,tI[u],tI[v],delta);
}
void input(){
	cin>>n;
	for(ll i=1;i<n;i++){
		ll u,v;
		cin>>u>>v;
		u++; v++;
		add_edge(u,v); add_edge(v,u);
	}
	cin>>m;
}
void solve(){
	dfs(1,0);
	sfs(1,0);
	build(1,1,n);
	for(ll i=1;i<=m;i++){
		char op;
		cin>>op;
		if(op=='A'){
			ll u,v,d;
			cin>>u>>v>>d;
			u++; v++;
			add_Tree(u,v,d);
		}else{
			ll u;
			cin>>u;
			u++;
			printf("%lld\n",query(1,tI[u],tO[u]));
		}
	}
}
int main(){
	input();
	solve();
	return 0;
}

2022/8/23 21:18
加载中...