BZOJ 4034 树上操作（树链剖分）

本文主要是介绍BZOJ 4034 树上操作（树链剖分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

思路：

这题让我对树剖的体会更加深入了
因为我们在组链（也就是划分轻重边）的时候，是使用dfs序来进行划分的，所以我们子树的节点也依旧是在一起的，也就是说，树剖的时候顺便标记下dfs完自己子树时候的标号，就可以顺便完成dfs序时的标号要求了

错误及反思：

这题没什么难的。。主要是对树剖的体会更深了

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1struct edge{int to,next;
}e[N*2];
long long segtree[N*4],lazy[N*4];
int tot,tid,q,n;
int top[N],si[N],fa[N],first[N],son[N],depth[N],id[N],to[N],val[N],rnk[N];void addedge(int x,int y){e[tot].to=y;e[tot].next=first[x];first[x]=tot++;e[tot].to=x;e[tot].next=first[y];first[y]=tot++;
}void dfs1(int now,int bef,int dep){fa[now]=bef;depth[now]=dep;si[now]=1;for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=bef){dfs1(e[i].to,now,dep+1);si[now]+=si[e[i].to];if(son[now]==-1) son[now]=e[i].to;else son[now]=si[e[i].to]>si[son[now]]?e[i].to:son[now];}
}void dfs2(int now,int tp){top[now]=tp;id[now]=tid++;if(son[now]!=-1) dfs2(son[now],tp);for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=fa[now]&&e[i].to!=son[now])dfs2(e[i].to,e[i].to);to[now]=tid-1;
}void init(){tot=0; tid=1;memset(first,-1,sizeof(first));memset(son,-1,sizeof(son));
}void pushup(int rt){segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
}void pushdown(int l,int r,int rt){if(lazy[rt]){int m=(l+r)/2;segtree[rt<<1]+=1ll*(m-l+1)*lazy[rt];lazy[rt<<1]+=lazy[rt];segtree[rt<<1|1]+=1ll*(r-m)*lazy[rt];lazy[rt<<1|1]+=lazy[rt];lazy[rt]=0;}
}void build(int l,int r,int rt){if(l==r){segtree[rt]=val[rnk[l]];return ;}int m=(l+r)/2;build(lson);build(rson);pushup(rt);
}void add(int L,int R,int v,int l,int r,int rt){if(L<=l&&R>=r){segtree[rt]+=1ll*v*(r-l+1);lazy[rt]+=v;return ;}pushdown(l,r,rt);int m=(l+r)/2;if(m>=L) add(L,R,v,lson);if(m<R) add(L,R,v,rson);pushup(rt);
}long long query(int L,int R,int l,int r,int rt){if(L<=l&&R>=r)return segtree[rt];pushdown(l,r,rt);int m=(l+r)/2;long long ans=0;if(m>=L) ans+=query(L,R,lson);if(m<R) ans+=query(L,R,rson);pushup(rt);return ans;
}
void cal(int L,int R){int f1=top[L],f2=top[R];long long ans=0;while(f1!=f2){if(depth[f1]<depth[f2]){swap(f1,f2);swap(L,R);}ans+=query(id[f1],id[L],1,tid-1,1);L=fa[f1];f1=top[L];}if(depth[L]>depth[R]) swap(L,R);ans+=query(id[L],id[R],1,tid-1,1);printf("%lld\n",ans);
}
int main(){init();scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%d",&val[i]);for(int i=0,u,v;i<n-1;i++){scanf("%d%d",&u,&v);addedge(u,v);}dfs1(1,1,1);dfs2(1,1);for(int i=1;i<=n;i++)rnk[id[i]]=i;build(1,n,1);while(q--){int ta; scanf("%d",&ta);if(ta==1){int tb,tc;scanf("%d%d",&tb,&tc);add(id[tb],id[tb],tc,1,n,1);}else if(ta==2){int tb,tc;scanf("%d%d",&tb,&tc);add(id[tb],to[tb],tc,1,n,1);}else{int tb;scanf("%d",&tb);cal(1,tb);}}
}