题目 模板
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f; const int maxn=2e5+10; struct node { int t,nxt; }edge[maxn]; int head[maxn],cnt; void init(int n) { cnt=0; memset(head,-1,sizeof head); } void addedge(int u,int v) { edge[cnt]=node{v,head[u]}; head[u]=cnt++; } int dep[maxn],dad[maxn],size[maxn],son[maxn]; int top[maxn],seg[maxn],id[maxn]; void dfs1(int u,int pre) { size[u]=1; son[u]=-1; int masize=0; for(int i=head[u];i!=-1;i=edge[i].nxt) { int v=edge[i].t; if(v==pre) continue; dad[v]=u; dep[v]=dep[u]+1; dfs1(v,u); size[u]+=size[v]; if(masize<size[v]) { masize=size[v]; son[u]=v; } } } void dfs2(int u,int fat,int &tag) { top[u]=fat; seg[u]=++tag; id[tag]=u; if(son[u]==-1) return; dfs2(son[u],fat,tag); for(int i=head[u];i!=-1;i=edge[i].nxt) { int v=edge[i].t; if(v==dad[u]||v==son[u]) continue; dfs2(v,v,tag); } } void cuttree(int root) { int tag=0; dep[root]=0; dad[root]=root; dfs1(root,root); dfs2(root,root,tag); } typedef long long ll; ll bit[maxn]; void add(int k,ll num,int limit) { for(;k<=limit;k+=k&(-k)) bit[k]+=num; } ll read(int k) { ll res=0; for(;k;k-=k&(-k)) res+=bit[k]; return res; } void update(int left,int right,ll num,int limit) { add(left,num,limit); add(right+1,-num,limit); } void modify(int u,int v,ll num,int limit) { int fu=top[u],fv=top[v]; while(fu!=fv) { if(dep[fu]>=dep[fv]) { update(seg[fu],seg[u],num,limit); u=dad[fu],fu=top[u]; } else { update(seg[fv],seg[v],num,limit); v=dad[fv],fv=top[v]; } } if(dep[u]>dep[v]) swap(u,v); update(seg[u],seg[v],num,limit); } int a[maxn]; bool solve() { int n,m,p,u,v,k; if(scanf("%d%d%d",&n,&m,&p)==EOF) return 0; init(n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } cuttree(1); memset(bit,0,sizeof bit); for(int i=1;i<=n;i++) update(seg[i],seg[i],a[i],n); char op[3]; while(p--) { scanf("%s",op); if(op[0]=='Q') { scanf("%d",&u); ll ans=read(seg[u]); printf("%lld\n",ans); } else { scanf("%d%d%d",&u,&v,&k); if(op[0]=='D') k=-k; modify(u,v,k,n); } } return 1; } int main() { while(solve()); }