1.前言:
以前初学者都会认为树链剖分是个很难的算法,其实很简单.大致思想就是把树分成链,然后用线段树进行一定操作即可.只是代码稍微有点长.
2.算法流程:
1.首先对于这颗树的每个点找到它的重儿子,树链剖分需要重构一下这颗树让重儿子的节点优先跑出,这里只需要一个dfs即可.
2.重构完树了之后呢?就只要把这颗树按节点序号投影到线段树即可.然后用线段树的操作来对于树进行操作.
3.对于模板题 一个很显然的结论,在树重构了之后,我对于子树u进行操作就是对于线段树区间(u,u+siz[u]-1)进行操作.然后对于树上路径是唯一的,我们可以采用倍增的思想对于u->v这条路径进行操作,这里我们需要记录一个东西,就是重链的起点是哪里,对于不是一颗重链的点,我们就可以一直跳.比较一下深度即可.
3.时间复杂度分析:
因为假如u->v为轻边,那么siz[v]<siz[u]/2的,否则为重边,如此可以判断轻边数量不超过logn的,然后线段树查询时logn的,所以时间复杂度就是的.
4.代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+500; ll n,m,r,p; ll w[N]; vector<int>v[N]; ll dep[N],siz[N],dfn[N],f[N]; //跑出深度,子树大小,重儿子,父亲. void dfs1(int u,int fa) { siz[u]=1;dep[u]=dep[fa]+1;f[u]=fa; int num=v[u].size(); for(int i=0;i<num;i++) { int son=v[u][i]; if(son==fa) continue; dfs1(son,u); siz[u]+=siz[son]; if(siz[son]>siz[dfn[u]]) dfn[u]=son; } } //跑出每个节点的下标以及处理它们的权值,然后统计重链的起点. ll id=0,idx[N],top[N],val[N]; void dfs2(int u,int topf) { idx[u]=++id; top[u]=topf; val[id]=w[u]; if(!dfn[u]) return; dfs2(dfn[u],topf); int num=v[u].size(); for(int i=0;i<num;i++) { int son=v[u][i]; if(idx[son]) continue; dfs2(son,son); } } //写一份有线段树区间修改,区间求和功能的树. struct Tree{ ll l,r,len,sum,lazy; }tr[N<<2]; void pushup(int u) { tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void pushdown(int u) { tr[u<<1].sum=(tr[u<<1].sum+tr[u].lazy*tr[u<<1].len%p)%p; tr[u<<1|1].sum=(tr[u<<1|1].sum+tr[u].lazy*tr[u<<1|1].len%p)%p; tr[u<<1].lazy=(tr[u<<1].lazy+tr[u].lazy)%p; tr[u<<1|1].lazy=(tr[u<<1|1].lazy+tr[u].lazy)%p; tr[u].lazy=0; } void build(int u,int l,int r) { tr[u].len=(r-l+1);tr[u].l=l;tr[u].r=r; if(l==r) { tr[u].l=tr[u].r=l; tr[u].sum=val[l]; return; }int mid=(l+r)>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } void add(int u,int L,int R,int k) { if(tr[u].r<L||R<tr[u].l) return; if(L<=tr[u].l&&tr[u].r<=R) { tr[u].sum=(tr[u].sum+k*(tr[u].len)%p)%p; tr[u].lazy=(tr[u].lazy+k)%p; return; }pushdown(u); add(u<<1,L,R,k); add(u<<1|1,L,R,k); pushup(u); } ll query(int u,int L,int R) { if(tr[u].r<L||R<tr[u].l) return 0; if(L<=tr[u].l&&tr[u].r<=R) return tr[u].sum%p; pushdown(u); return (query(u<<1,L,R)+query(u<<1|1,L,R))%p; } //实现v->u的修改以及查询操作. void Treeadd(int x,int y,int k) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); add(1,idx[top[x]],idx[x],k); x=f[top[x]]; } if(dep[x]>dep[y]) swap(x,y); add(1,idx[x],idx[y],k); } ll Treesum(int x,int y) { ll ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans=(ans+query(1,idx[top[x]],idx[x]))%p; x=f[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans=(ans+query(1,idx[x],idx[y]))%p; return ans; } int main() { scanf("%lld%lld%lld%lld",&n,&m,&r,&p); for(int i=1;i<=n;i++) scanf("%lld",&w[i]); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } dfs1(r,r); dfs2(r,r); build(1,1,n); while(m--) { int op,x,y,z; scanf("%d",&op); if(op==1) { scanf("%d%d%d",&x,&y,&z); Treeadd(x,y,z%p); } else if(op==2) { scanf("%d%d",&x,&y); printf("%lld\n",Treesum(x,y)); } else if(op==3) { scanf("%d%d",&x,&z); add(1,idx[x],idx[x]+siz[x]-1,z%p); } else { scanf("%d",&x); printf("%lld\n",query(1,idx[x],idx[x]+siz[x]-1)); } } return 0; }