一：用处
对一棵树分成几条链，把树形变为线性，减少处理难度 需要处理的问题：
1.将树从x到y结点最短路径上所有节点的值都加上z
2.求树从x到y结点最短路径上所有节点的值之和
3.将以x为根节点的子树内所有节点值都加上z
4.求以x为根节点的子树内所有节点值之和
二：相关概念：
1.重儿子：对于每一个非叶子节点，它的儿子中以那个儿子为根的子树节点数（包括自身）最大的儿子为该节点的重儿子
2.轻儿子：非重儿子
3.重边：一个父节点与其重儿子的连边
4.轻边：非重边
5.重链：相邻重边相连形成的链
tips：叶子结点若为轻儿子，则自成一条长度为1的链
重链以轻儿子或根节点为起点
三：常规操作
1.预处理
（1）dfs1：
处理：
各点深度； 各点重儿子编号； 各点最大子树大小 ；各点父亲
代码：
void dfs1(int now,int fa,int deep) { siz[now]=1; fat[now]=fa; dep[now]=deep; zs=-1; for(int i=head[now];i;i=nxt[i]) { if(to[i]==now) continue; //别忘了 dfs1(to[i],now,deep+1); siz[now]+=siz[to[i]]; if(siz[to[i]]>zs)//处理重儿子 zhoson[now]=to[i],zs=siz[to[i]]; } }
（2）dfs2
处理：
标记每个点的新编号（线段树中编号）
赋值每个点的初始值到新编号上
处理每个点所在链的顶端
处理每条链
顺序规定：先重后轻
代码：
void dfs2(int now,int top) { tp[now]=top; id[now]=++cnt; wt[cnt]=w[x]; if(!zhoson[now]) return; dfs2(zhoson[now],top); for(int i=head[now];i;i=nxt[i]) { if(to[i]==fat[now]||to[i]==zhoson[now]) continue; dfs2(to[i],to[i]); } }
2.功能实现
1.查询两点间距离
方法：每次选定两点所在链中深度较大的，加上它到其链起点的权值，然后跳到链起点的父节点重复操作，直至两点在同一条链上。
int qiurange(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); res=0; query(1,1,n,tid[top[x]],tid[x]); ans=(ans+res)%mod; x=fat[top[x]]; } if(deep[x]>deep[y]) swap(x,y); res=0; query(1,1,n,tid[x],tid[y]); ans=(ans+res)%mod; return ans; }
2.两点间路径修改：
同1，反复跳并update（线段树）
void uprange(int x,int y,int k) { k%=mod; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); update(1,1,n,tid[top[x]],tid[x],k); x=fat[top[x]]; } if(deep[x]>deep[y]) swap(x,y); update(1,1,n,tid[x],tid[y],k); }3.子树修改
上边提到过，子树中节点的编号是连续的，因此在线段树上也是一段连续的区间，相当于线段树区间修改
void updSon(int x,int k) { update(1,1,n,tid[x],tid[x]+siz[x]-1,k); }4.子树查询
只要直接维护即可。（区间的起点是该子树根节点，大小是子树大小）
int qSon(int x) { res=0; query(1,1,n,tid[x],tid[x]+siz[x]-1); return res; }完整代码如下，除了上面的部分还要有线段树的基本操作函数（因此码量感人）：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define maxn 100005 #define mid (l+r>>1) #define len (r-l+1) #define ls id<<1 #define rs id<<1|1 using namespace std; int cnt,head[maxn],nxt[maxn << 1],to[maxn << 1]; int w[maxn],wt[maxn],tidnum,siz[maxn],deep[maxn],son[maxn],fat[maxn],tid[maxn],top[maxn]; int a[maxn << 2],laz[maxn << 2]; int res=0,n,m,r,mod; void addedge(int x,int y) { to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; } void pushdown(int rt,int l,int r) { (laz[rt<<1]+=laz[rt]) %= mod; (laz[rt<<1|1]+=laz[rt]) %= mod; a[rt<<1]+=laz[rt]*(mid - l + 1); a[rt<<1|1]+=laz[rt]*(r - mid); a[rt<<1]%=mod; a[rt<<1|1]%=mod; laz[rt]=0; } void build(int id,int l,int r) { if(l==r) { a[id]=wt[l]; if(a[id]>mod) a[id]%=mod; return; } build(ls,l,mid); build(rs,mid+1,r); a[id]=(a[id<<1]+a[id<<1|1])%mod; } void query(int id,int l,int r,int tol,int tor) { if(tol<=l&&r<=tor) { res+=a[id]; res%=mod; return; } else { if(laz[id]) pushdown(id,l,r); if(tol<=mid) query(ls,l,mid,tol,tor); if(tor>mid) query(rs,mid+1,r,tol,tor); } } void update(int id,int l,int r,int tol,int tor,int k) { if(tol<=l&&r<=tor) { laz[id]+=k; a[id]+=k*len; a[id] %= mod; laz[id] %= mod; } else { if(laz[id]) pushdown(id,l,r); if(tol<=mid) update(ls,l,mid,tol,tor,k); if(tor>mid) update(rs,mid+1,r,tol,tor,k); a[id]=(a[id<<1]+a[id<<1|1])%mod; } } int qiurange(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); res=0; query(1,1,n,tid[top[x]],tid[x]); ans=(ans+res)%mod; x=fat[top[x]]; } if(deep[x]>deep[y]) swap(x,y); res=0; query(1,1,n,tid[x],tid[y]); ans=(ans+res)%mod; return ans; } void uprange(int x,int y,int k) { k%=mod; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); update(1,1,n,tid[top[x]],tid[x],k); x=fat[top[x]]; } if(deep[x]>deep[y]) swap(x,y); update(1,1,n,tid[x],tid[y],k); } int qSon(int x) { res=0; query(1,1,n,tid[x],tid[x]+siz[x]-1); return res; } void updSon(int x,int k) { update(1,1,n,tid[x],tid[x]+siz[x]-1,k); } void dfs1(int x,int f,int deeep) { deep[x]=deeep; fat[x]=f; siz[x]=1; int maxson=-1; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(y==f) continue; dfs1(y,x,deeep+1); siz[x]+=siz[y]; if(siz[y]>maxson) son[x]=y,maxson=siz[y]; } } void dfs2(int id,int tp) { tid[id]=++tidnum; wt[tidnum]=w[id]; top[id]=tp; if(!son[id]) return; dfs2(son[id],tp); for(int i=head[id];i;i=nxt[i]) { if(to[i]==fat[id]||to[i]==son[id]) continue; dfs2(to[i],to[i]); } } int main() { scanf("%d%d%d%d",&n,&m,&r,&mod); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); addedge(a,b); addedge(b,a); } dfs1(r,0,1); dfs2(r,r); build(1,1,n); while(m--) { int t,x,y,z; scanf("%d",&t); if(t==1) { scanf("%d%d%d",&x,&y,&z); uprange(x,y,z); } else if(t==2) { scanf("%d%d",&x,&y); printf("%d\n",qiurange(x,y)); } else if(t==3) { scanf("%d%d",&x,&y); updSon(x,y); } else { scanf("%d",&x); printf("%d\n",qSon(x)); } } return 0; }
转载于:https://www.cnblogs.com/charlesss/p/10474190.html
