输入样例不知道为什么为什么会输出一串奇怪的数字。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define N 100005
using namespace std;
int n,m;
int tot,cnt;
int head[N],son[N];
int dep[N],fa[N],size[N];
int idx[N],top[N];
struct node{
int next,to;
}e[N<<1];
void add(int u,int v){
e[++tot].to=v;
e[tot].next=head[u];
head[u]=tot;
}
void dfs1(int u,int f){
dep[u]=dep[f]+1;
fa[u]=f;
size[u]=1;
for(int i=head[u],v;i;i=e[i].next){
v=e[i].to;
if(v==f) continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])
son[u]=v;
}
}
void dfs2(int u,int topf){
idx[u]=++cnt;
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=head[u],v;i;i=e[i].next){
v=e[i].to;
if(v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
}
struct Segment_Tree{
int w[N<<1],lazy[N<<1];
#define lson (k<<1)
#define rson (k<<1|1)
void push_up(int k){
w[k]=w[lson]+w[rson];
}
void push_down(int k,int len){
if(lazy[k]==0) return;
lazy[lson]=lazy[k];
lazy[rson]=lazy[k];
w[lson]=lazy[k]*(len-(len>>1));
w[rson]=lazy[k]*(len>>1);
lazy[k]=0;
}
void build(int k,int l,int r){
if(l==r){
w[k]=0;
lazy[k]=0;
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
push_up(k);
}
void update(int L,int R,int k,int l,int r,int x){
if(L<=l && r<=R){
lazy[k]=x;
w[k]=x*(r-l+1);
return;
}
int mid=(l+r)>>1;
push_down(k,r-l+1);
if(L<=mid) update(L,R,lson,l,mid,x);
if(R>mid) update(L,R,rson,mid+1,r,x);
push_up(k);
}
int query(int L,int R,int k,int l,int r){
if(L<=l && r<=R) return w[k];
int mid=(l+r)>>1,res=0;
push_down(k,r-l+1);
if(L<=mid) res+=query(L,R,lson,l,mid);
if(R>mid) res+=query(L,R,rson,mid+1,r);
push_up(k);
}
}tree;
void updrange(int u,int v,int w){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
tree.update(idx[top[u]],idx[u],1,1,n,w);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(v,u);
tree.update(idx[u],idx[v],1,1,n,w);
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
add(u+1,v+1);
add(v+1,u+1);
}
dfs1(1,0);
dfs2(1,1);
tree.build(1,1,n);
scanf("%d",&m);
char opt;
int u,v,t;
while(m--){
scanf(" %c",&opt);
if(opt=='A'){
scanf("%d%d%d",&u,&v,&t);
updrange(u+1,v+1,t);
}
else{
scanf("%d",&u);
printf("%d\n",tree.query(idx[u+1],idx[u+1]+size[u+1]-1,1,1,n));
}
}
return 0;
}