P3833 [SHOI2012]魔法树
省选考树剖裸题。。。
code：
#include <iostream>
#include <cstdio>
#define ls(o) o<<1
#define rs(o) o<<1|1
#define int long long
using namespace std;
const int wx=100017;
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}
return sum*f;
}
int dfn[wx],tid[wx];
int dep[wx],f[wx],size[wx],son[wx];
int top[wx];
int head[wx],a[wx];
int n,m,num,tot;
char opt[17];
struct val_tree{
int l,r,tag,sum;
#define tag(o) t[o].tag
#define sum(o) t[o].sum
}t[wx*4];
void up(int o){
sum(o)=sum(ls(o))+sum(rs(o));
}
void down(int o){
if(tag(o)){
sum(ls(o))+=tag(o)*(t[ls(o)].r-t[ls(o)].l+1);
sum(rs(o))+=tag(o)*(t[rs(o)].r-t[rs(o)].l+1);
tag(ls(o))+=tag(o); tag(rs(o))+=tag(o);
tag(o)=0;
}
}
void build(int o,int l,int r){
t[o].l=l;t[o].r=r;
if(l==r){sum(o)=a[tid[l]];return ;}
int mid=t[o].l+t[o].r>>1;
if(l<=mid)build(ls(o),l,mid);
if(r>mid)build(rs(o),mid+1,r);
up(o);
}
void update_t(int o,int l,int r,int k){
if(l<=t[o].l&&t[o].r<=r){
sum(o)+=k*(t[o].r-t[o].l+1);
tag(o)+=k; return ;
}
down(o);
int mid=t[o].l+t[o].r>>1;
if(l<=mid)update_t(ls(o),l,r,k);
if(r>mid)update_t(rs(o),l,r,k);
up(o);
}
int query_t(int o,int l,int r){
if(l<=t[o].l&&t[o].r<=r){
return sum(o);
}
down(o); int sum=0;
int mid=t[o].l+t[o].r>>1;
if(l<=mid)sum+=query_t(ls(o),l,r);
if(r>mid)sum+=query_t(rs(o),l,r);
return sum;
}
//~~~~~~~~~~~~~~~~~~~~~~~~
struct e{
int nxt,to;
}edge[wx*2];
void add(int from,int to){
edge[++num].nxt=head[from];
edge[num].to=to;
head[from]=num;
}
void first_dfs(int u,int fa){
f[u]=fa;dep[u]=dep[fa]+1;
size[u]=1;
int maxson=-1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa)continue;
first_dfs(v,u);
size[u]+=size[v];
if(size[v]>maxson){
son[u]=v; maxson=size[v];
}
}
}
void second_dfs(int u,int topf){
dfn[u]=++tot;
top[u]=topf;
tid[tot]=u;
if(son[u]){
second_dfs(son[u],topf);
}
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(dfn[v]||v==son[u])continue;
second_dfs(v,v);
}
}
void update(int x,int y,int k){
int fx=top[x]; int fy=top[y];
while(fx!=fy){
if(dep[fx]>dep[fy]){
update_t(1,dfn[fx],dfn[x],k);
x=f[fx];
}
else{
update_t(1,dfn[fy],dfn[y],k);
y=f[fy];
}
fx=top[x]; fy=top[y];
}
if(dfn[x]>dfn[y]) swap(x,y);
update_t(1,dfn[x],dfn[y],k);
return ;
}
signed main(){
n=read();
for(int i=1;i<n;i++){
int x,y;
x=read(); y=read();
x++; y++;
add(x,y);add(y,x);
}
first_dfs(1,0);
second_dfs(1,1);
build(1,1,n);
m=read();
for(int i=1;i<=m;i++){
scanf("%s",opt+1);
if(opt[1]=='A'){
int x,y,z;
x=read();y=read();z=read();
x++; y++;
update(x,y,z);
}
else{
int x; x=read(); x++;
printf("%lld\n",query_t(1,dfn[x],dfn[x]+size[x]-1));
}
}
return 0;
}