爱站程序员基地Aragorn’s Story HDU – 3966
题解：老套路了，轻重链剖分线段树维护
#include <iostream>#include <cstdio>#include <algorithm>#include <memory.h>#define mid ((l+r)>>1)using namespace std;const int maxn=2e5;typedef long long ll;struct E{int v,w,next;};E edge[maxn];int tot=0;int lenid=0;int arr[maxn];int sum[maxn];int head[maxn];int fa[maxn];int son[maxn];int id[maxn];int dep[maxn];int size[maxn];int top[maxn];ll tree[maxn<<2];int lazy[maxn<<2];int n,m,p;void add(int u,int v,int w){edge[tot].w=w;edge[tot].v=v;edge[tot].next=head[u];head[u]=tot++;}void dfs1(int u,int f,int d){dep[u]=d;size[u]=1;son[u]=0;fa[u]=f;for(int i=head[u];~i;i=edge[i].next){int v=edge[i].v;if(v!=f){dfs1(v,u,d+1);size[u]+=size[v];if(son[u]==0 || size[son[u]]<size[v]){son[u]=v;}}}}void dfs2(int u,int f){id[u]=++lenid;sum[lenid]=arr[u];top[u]=f;if(son[u]){dfs2(son[u],f);}for(int i=head[u];~i;i=edge[i].next){int v=edge[i].v;if(v!=fa[u] && v!=son[u]){dfs2(v,v);}}}void pushup(int rt){tree[rt]=tree[rt<<1]+tree[rt<<1|1];}void pushdown(int l,int r,int rt){if(lazy[rt]!=0){int len=(r-l+1);lazy[rt<<1]+=lazy[rt];lazy[rt<<1|1]+=lazy[rt];tree[rt<<1]+=lazy[rt]*(len-(len>>1));tree[rt<<1|1]+=(len>>1)*lazy[rt];lazy[rt]=0;}}void build(int l,int r,int rt){lazy[rt]=0;if(l==r){tree[rt]=sum[l];return ;}build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);}void update(int a,int b,int c,int l,int r,int rt){if(a<=l && b>=r){lazy[rt]+=c;tree[rt]+=ll((r-l+1)*c);// cout<<tree[rt]<<endl;// cout<<rt<<\" \"<<lazy[rt]<<endl;return ;}pushdown(l,r,rt);if(a<=mid){update(a,b,c,l,mid,rt<<1);}if(b>mid){update(a,b,c,mid+1,r,rt<<1|1);}pushup(rt);}ll query(int x,int l,int r,int rt){if(l==r){return tree[rt];}// cout<<rt<<\" \"<<lazy[rt]<<endl;pushdown(l,r,rt);if(x<=mid){return query(x,l,mid,rt<<1);}else{return query(x,mid+1,r,rt<<1|1);}pushup(rt);}void lca(int x,int y,int add){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]){swap(x,y);}update(id[top[x]],id[x],add,1,n,1);x=fa[top[x]];}if(dep[x]>dep[y]){swap(x,y);}update(id[x],id[y],add,1,n,1);}void init(){memset(head,-1,sizeof(head));lenid=tot=0;}int main(){while(~scanf(\"%d%d%d\",&n,&m,&p)){init();for(int i=1;i<=n;i++){scanf(\"%d\",&arr[i]);}for(int i=1;i<n;i++){int u,v;scanf(\"%d%d\",&u,&v);add(u,v,0);add(v,u,0);}dfs1(1,0,1);dfs2(1,0);// for(int i=1;i<=lenid;i++){// cout<<id[i]<<\" \";// }build(1,n,1);while(p--){char pos;scanf(\" %c\",&pos);if(pos==\'I\'){int u,v,add;scanf(\"%d%d%d\",&u,&v,&add);lca(u,v,add);}else if(pos==\'D\'){int u,v,add;scanf(\"%d%d%d\",&u,&v,&add);lca(u,v,-add);}else if(pos==\'Q\'){int u;scanf(\"%d\",&u);printf(\"%lld\\n\",query(id[u],1,n,1));}}}return 0;}
