复习板子.
树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等.
树剖的思路其实不难, 主要是代码长… 考虑如何把一棵树通过编号处理成尽量少的链, 同时保证每棵子树/每条链的编号都连续. 容易发现dfs序就满足前者, 这样就保证了每棵子树都在一个连续区间上. 再考虑一个贪心策略, 划分链的时候先尽量把子树节点多的节点(重儿子)纳入一条链, 得到一条重链, 其它轻儿子以同样的方法递归处理, 最终得到的链的总数是$latex \log n$级别的. 再加上一次区间维护/操作的复杂度为$latex \log n$, 总复杂度就是$latex O(n \log^2 n)$.
#include<cstdio> #define in inline #define re register #define ll long long #define lc p<<1 #define rc (p<<1)+1 in int read() { int s=0,b=0;char ch; do{ch=getchar();if(ch=='-') b=1;}while(ch<'0'||ch>'9'); while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();} return b?-s:s; } const int N=100001; int n,m,root,yyb; struct edge{ int t,nxt; }e[N*2]; int cnt,head[N]; int w[N],id[N],wid[N],f[N],d[N],subt[N],son[N],top[N]; //w节点原始权值;f[x]x的父亲;d[x]x节点的深度;subt[x]以x为根的子树的节点数;son[x]x的重儿子;top[x]x节点所在的链的链顶 //id[x]x节点树剖后的新编号;wid按新编号存放的节点权值;(树->链,方便在线段树上处理) in void add(int f,int t) { ++cnt; e[cnt].t=t,e[cnt].nxt=head[f],head[f]=cnt; ++cnt; e[cnt].t=f,e[cnt].nxt=head[t],head[t]=cnt; } //以下是线段树板子 struct SegmentTree{ int l,r,sum,add; }t[N*4]; void build(int p,int l,int r) { t[p].l=l,t[p].r=r; if(l==r) {t[p].sum=wid[l];return;} int mid=(l+r)>>1; build(lc,l,mid); build(rc,mid+1,r); t[p].sum=(t[lc].sum+t[rc].sum)%yyb; } in void spread(int p) { if(!t[p].add) return; t[lc].add+=t[p].add,t[rc].add+=t[p].add; t[lc].sum+=t[p].add*(t[lc].r-t[lc].l+1); //t[lc,rc].add原先的值已经加入t[lc,rc].sum中, 这里应用t[p].add来乘而非t[lc,rc].add t[rc].sum+=t[p].add*(t[rc].r-t[rc].l+1); t[p].add=0; t[lc].sum%=yyb,t[rc].sum%=yyb; } int ask(int p,int l,int r) { if(l<=t[p].l && t[p].r<=r) return t[p].sum%yyb; spread(p); int mid=(t[p].l+t[p].r)>>1,ans=0;//不是 (l+r)>>1 !!!又错这里!!! if(l<=mid) ans+=ask(lc,l,r); if(r>mid) ans+=ask(rc,l,r); return ans%yyb; } void update(int p,int l,int r,int a) { if(l<=t[p].l && t[p].r<=r){t[p].add+=a,t[p].sum+=a*(t[p].r-t[p].l+1),t[p].sum%=yyb;return;} //同line54, 这里是a*而不是t[p].add* spread(p); int mid=(t[p].l+t[p].r)>>1;//不是 (l+r)>>1 !!!又错这里!!! if(l<=mid) update(lc,l,r,a); if(r>mid) update(rc,l,r,a); t[p].sum=(t[lc].sum+t[rc].sum)%yyb;//你TM修改了不更新 } //以上是线段树板子 void dfs1(int now,int fa) { //第一次dfs: 预处理深度, 父亲, 子树大小, 重儿子 d[now]=d[fa]+1,f[now]=fa,subt[now]=1; int maxson=0; for(re int i=head[now];i;i=e[i].nxt) { if(e[i].t==fa) continue; dfs1(e[i].t,now); subt[now]+=subt[e[i].t]; if(subt[e[i].t]>maxson) maxson=subt[e[i].t],son[now]=e[i].t; } } void dfs2(int now,int topfa) { //第二次dfs: 把树编号, 剖分成一条条链, 处理出top[] ++cnt; id[now]=cnt,wid[cnt]=w[now],top[now]=topfa; if(!son[now]) return;//叶子节点 dfs2(son[now],topfa); //重链剖分: 先递归重链, 所以每条重链的新编号是连续的 //又因为是dfs, 所以每个子树的新编号也是连续的 //这样就转化为线性区间了 for(re int i=head[now];i;i=e[i].nxt) if(e[i].t!=f[now] && e[i].t!=son[now]) dfs2(e[i].t,e[i].t);//每个轻儿子都有一条以它为topfa的链 } in int aksr(int x,int y) { //求x-y最短路径经过的点权之和: 设所在链顶端深度深的点为x //ans加上x到top[x]这段区间的点权和, 再x跳到fa[top[x]] //重复, 直至x,y在一条链上(top[x]==top[y]), 此时ans加上x-y这段线性连续区间和即可 int ans=0; while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) x^=y,y^=x,x^=y; ans+=ask(1,id[top[x]],id[x]); ans%=yyb; x=f[top[x]]; } if(d[x]<d[y]) x^=y,y^=x,x^=y; ans+=ask(1,id[y],id[x]); return ans%yyb; } in void updr(int x,int y,int a) { //x-y最短路径每个点+=a: 同上 while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) x^=y,y^=x,x^=y; update(1,id[top[x]],id[x],a%yyb); x=f[top[x]]; } if(d[x]<d[y]) x^=y,y^=x,x^=y; update(1,id[y],id[x],a%yyb); } //对于x为根的整个子树的处理: x子树节点新编号为id[x]~id[x]+subt[x]-1, 处理这段线性连续区间即可 in int asksub(int x) {return ask(1,id[x],id[x]+subt[x]-1);} in void updsub(int x,int a) {update(1,id[x],id[x]+subt[x]-1,a);} signed main() { n=read(),m=read(),root=read(),yyb=read(); for(re int i=1;i<=n;++i) w[i]=read(); for(re int i=1;i<=n-1;++i){int u=read(),v=read();add(u,v);} dfs1(root,0); cnt=0; dfs2(root,root); build(1,1,n);//树剖后按wid建线段树,树->链 for(re int i=1;i<=m;++i) { int x,y,z; x=read(); if(x==1){x=read(),y=read(),z=read();updr(x,y,z);} else if(x==2){x=read(),y=read();printf("%d\n",aksr(x,y));} else if(x==3){x=read(),y=read();updsub(x,y);} else{x=read();printf("%d\n",asksub(x));} } return 0; }
最新评论