RT,代码如下
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<cstdio>
#define R(i,a,n) for(register long long i=(a);i<=(n);i++)
#define F(i,a,n) for(register long long i=(n);i>=(a);i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> void read(T &x) {
x = 0; int f = 0; char ch = getchar();
while (ch < '0' || ch > '9') {f |= (ch == '-'); ch = getchar();}
while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
x = f ? -x : x;
return;
}
using namespace std;
const ll maxn=1e5+10;
struct edge{ll nex,to;}e[2*maxn];
struct note{ll l,r,sum,add;}a[maxn*2];
ll n,m,r,rt,mod,v[maxn],head[maxn],cnt,f[maxn],d[maxn],son[maxn],size[maxn],top[maxn],id[maxn],rk[maxn];
void build(ll u,ll v){e[++cnt].nex=head[u];e[cnt].to=v;head[u]=cnt;}
void dfs1(ll x,ll fa,ll depth)
{
f[x]=fa;size[x]=1;d[x]=depth;
for(int i=head[x];i;i=e[i].nex)
{
ll y=e[i].to;
if(y==fa) continue;
dfs1(y,x,depth+1);
size[x]+=size[y];
if(size[son[x]]<size[y]) son[x]=y;
}
}
void dfs2(ll x,ll tp)
{
top[x]=tp;id[x]=++cnt;rk[cnt]=x;
if(son[x]) dfs2(son[x],tp);
for(ll i=head[x];i;i=e[i].nex)
{
ll y=e[i].to;
if(son[x]!=y&&y!=f[x])dfs2(y,y);
}
}
void pup(ll x)
{
a[x].sum=a[2*x].sum+a[2*x+1].sum;
}
void built(ll l,ll r,ll x)
{
a[x].l=l;a[x].r=r;
if(l==r)
{
a[x].sum=0;
return ;
}
ll mid=(l+r)>>1;
built(l,mid,2*x);built(mid+1,r,2*x+1);
pup(x);
return ;
}
ll len(ll x)
{
return a[x].r-a[x].l+1;
}
void spread(ll x)
{
if(a[x].add)
{
ll ls=2*x,rs=2*x+1,lz=a[x].add;
a[ls].sum+=len(ls)*lz;a[rs].sum+=len(rs)*lz;
a[ls].add+=lz;a[rs].add+=lz;
a[x].add=0;
}
}
void change(ll l,ll r,ll c,ll x)
{
if(a[x].l>=l&&a[x].r<=r)
{
a[x].sum+=len(x)*c;
a[x].add+=c;
return ;
}
spread(x);
int mid=(a[x].l+a[x].r)>>1;
if(l<=mid) change(l,r,c,2*x);
if(r>mid) change(l,r,c,2*x+1);
pup(x); return ;
}
ll ask(ll l,ll r,ll x)
{
if(a[x].l>=l&&a[x].r<=r)
{
return a[x].sum;
}
spread(x);
ll mid=(a[x].l+a[x].r)>>1,ans=0;
if(l<=mid) ans+=ask(l,r,2*x);
if(r>mid) ans+=ask(l,r,2*x+1);
return ans;
}
void lcasum(ll x,ll y,ll c)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
change(id[top[x]],id[x],c,1);
x=f[top[x]];
}
if(d[x]<d[y]) swap(x,y);
change(rk[y],rk[x],c,1);
}
/*void ModifyOnTree(int x,int y,int k)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
modify(rk[top[x]],rk[x],1,k);x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
modify(rk[y],rk[x],1,k);
}*/
ll asktree(ll x,ll y)
{
ll ans=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans+=ask(rk[top[x]],rk[x],1);
x=f[top[x]];
}
if(id[x]<id[y]) swap(x,y);
ans+=ask(rk[y],rk[x],1);
return ans;
}
int main()
{
read(n);
R(i,1,n-1)
{
ll x,y;
read(x);read(y);
build(x,y);build(y,x);
}
dfs1(0,0,1);cnt=0;dfs2(0,0);built(1,n,1);
read(m);
R(i,1,m)
{
char op;
cin>>op;
if(op=='A')
{
ll u,v,c;
read(u);read(v);read(c);
lcasum(u,v,c);
}
else
{
ll x;
read(x);
printf("%d\n",ask(id[x],id[x]+size[x]-1,1));
}
}
return 0;
}