一：用处
对一棵树分成几条链，把树形变为线性，减少处理难度
需要处理的问题：
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
",qiurange(x,y));
}
else if(t==3)
{
scanf("%d%d",&x,&y);
updSon(x,y);
}
else
{
scanf("%d",&x);
printf("%d
",qSon(x));
}
}
return 0;
}