本蒟蒻写了个树剖的板子然而WA完了,而且自己输出的和数据毫无规律的不同,求各位大佬支援一下。
#include<bits/stdc++.h>
using namespace std;
#define lc (p<<1)
#define rc (p<<1|1)
#define N 100010
typedef long long ll;
ll read(){
ll sum=0,neg=1;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') neg=-1,c=getchar();
while(c>='0'&&c<='9') sum=(sum<<3)+(sum<<1)+c-'0',c=getchar();
return sum*neg;
}
struct Edge{
int u,v;
}e[N<<1];
int first[N],nxt[N<<1],cnt=0;
int depth[N],size[N],son[N],top[N],fa[N],wu[N];
int ide[N],dfs_clock=0;
long long val[N];
void AddEdge(int u,int v){
e[++cnt].u=u;e[cnt].v=v;
nxt[cnt]=first[u];first[u]=cnt;
}
struct Node{
int l,r,lazy;
ll sum;
};
struct SegmentTree{
Node T[N<<2];
inline void pushnow(int p,int v){
T[p].sum+=(T[p].r-T[p].l+1)*v;
T[p].lazy+=v;
}
inline void pushup(ll p){
T[p].sum=T[lc].sum+T[rc].sum;
}
inline void pushdown(ll p){
if(!T[p].lazy){
pushnow(lc,T[p].lazy);
pushnow(rc,T[p].lazy);
T[p].lazy=0;
}
}
void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r){
T[p].sum=val[wu[l]]; T[p].lazy=0;
return;
}
ll mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
}
void update(ll p,ll ql,ll qr,ll v){
if(ql<=T[p].l&&qr>=T[p].r){
pushnow(p,v);
return;
}
ll mid=(T[p].l+T[p].r)>>1;
pushdown(p);
if(ql<=mid) update(lc,ql,qr,v);
if(qr>mid) update(rc,ql,qr,v);
pushup(p);
}
ll query(int p,int ql,int qr){
if(ql<=T[p].l&&qr>=T[p].r) return T[p].sum;
ll mid=(T[p].l+T[p].r)>>1;
pushdown(p);
ll ans=0;
if(ql<=mid) ans+=query(lc,ql,qr);
if(qr>mid) ans+=query(rc,ql,qr);
pushup(p);
return ans;
}
}Tree;
void dfs1(int u){
size[u]=1;
depth[u]=depth[fa[u]]+1;
for(int i=first[u];i;i=nxt[i]){
int v=e[i].v;
if(v==fa[u]) continue;
fa[v]=u;
dfs1(v);
size[u]+=size[v];
if(size[son[u]]<size[v]) son[u]=v;
}
}
void dfs2(int u,int topf){
++dfs_clock;
top[u]=topf;
ide[u]=dfs_clock;
wu[ide[u]]=u;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=first[u];i;i=nxt[i]){
int v=e[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
void modify_path(int u,int v,int d){
while(top[u]!=top[v]){
if(depth[top[u]]<depth[top[v]]) swap(u,v);
Tree.update(1,ide[top[u]],ide[u],d);
u=fa[top[u]];
}
if(depth[u]>depth[v]) swap(u,v);
Tree.update(1,ide[u],ide[v],d);
}
ll n;
int main(){
n=read();
for(int i=1;i<n;i++){
int a,b;
a=read(); b=read();
a++; b++;
//cout<<a<<" "<<b<<endl;
AddEdge(a,b);
AddEdge(b,a);
}
dfs1(1);
dfs2(1,1);
Tree.build(1,1,n);
/*for(int i=1;i<=n;i++) cout<<ide[i]<<" ";
cout<<endl;
for(int i=1;i<=n;i++) cout<<fa[i]<<" ";*/
int q;
q=read();
for(int i=1;i<=q;i++){
char cmd;
scanf("%s",&cmd);
if(cmd=='A'){
int u,v,d;
u=read(); v=read(); d=read();
u++; v++;
modify_path(u,v,d);
}
else if(cmd=='Q'){
int u;
u=read();
u++;
ll ans=Tree.query(1,ide[u],ide[u]+size[u]-1);
printf("%lld\n",ans);
}
}
}