锰锌刚学树剖114514ms,0pts求调
查看原帖
锰锌刚学树剖114514ms,0pts求调
739250
Smi1EMAsk楼主2023/2/19 18:17

RT

//OOOOOOOOOOOOOOOOrz
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int rd(){
	int num=0,sign=1; char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') sign=-1; ch=getchar();}
	while (ch>='0'&&ch<='9') num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num*sign;
}
const int N=1e5+7;
int siz[N],top[N],son[N],fa[N],dep[N],idx[N];
int n,m,cnt;
vector <int> g[N];
void dfs1(int x,int f){
	fa[x]=f;dep[x]=dep[f]+1;
	siz[x]=1;
	for(int i=0;i<g[x].size();i++){
		int y=g[x][i];
		if(y==f) continue;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son[x]=y;
	}
}
void dfs2(int x,int topf){
	top[x]=topf;idx[x]=++cnt;
	if(son[x]) dfs2(son[x],topf);
	for(int i=0;i<g[x].size();i++){
		int y=g[x][i];
		if(!idx[y]) dfs2(y,y);
	}
}
struct SGT{
	int data[N<<2],lazy[N<<2];
	int L[N<<2],R[N<<2];
	void updata(int id){
		data[id]=data[id<<1]+data[id<<1|1];
	}
	void build(int l,int r,int id){
		L[id]=l;R[id]=r;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(l,mid,id<<1);
		build(mid+1,r,id<<1|1);
	}
	void Add(int id,int k){
		data[id]+=(R[id]-L[id]+1)*k;
		lazy[id]+=k;
	}
	void pushdown(int id){
		if(!lazy[id]) return ;
		Add(id<<1,lazy[id]);
		Add(id<<1|1,lazy[id]);
		lazy[id]=0;
	}
	void add(int l,int r,int id,int k){
		if(l<=L[id]&&R[id]<=r) return Add(id,k),void();
		pushdown(id);
		if(R[id<<1]>=l) add(l,r,id<<1,k);
		if(L[id<<1|1]<=r) add(l,r,id<<1|1,k);
		updata(id);
	}
	void TreeAdd(int x,int y,int k){
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]]) swap(x,y);
			add(idx[top[x]],idx[x],1,k);
			x=fa[top[x]];
		}
		if(dep[x]>dep[y]) swap(x,y);
		add(idx[x],idx[y],1,k);
	}
	int Sum(int l,int r,int id){
		if(l<=L[id]&&R[id]<=r) return data[id];
		int res=0;
		if(R[id<<1]>=l) res+=Sum(l,r,id<<1);
		if(L[id<<1|1]<=r) res+=Sum(l,r,id<<1|1);
		return res;
	}
}t;
signed main(){
	n=rd();
	for(int i=1;i<n;i++){
		int x=rd()+1,y=rd()+1;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs1(1,0);dfs2(1,1);
	t.build(1,n,1);
	m=rd();
	while(m--){
		char op[10]="";
		scanf("%s",op);
		if(op[0]=='A'){
			int u=rd()+1,v=rd()+1,k=rd();
			t.TreeAdd(u,v,k);
		}
		else{
			int x=rd()+1;
			printf("%lld\n",t.Sum(idx[x],idx[x]+siz[x]-1,1));
		}
	}
	return 0;
}

2023/2/19 18:17
加载中...