树链剖分 时间！！！！
首先要学会线段树。由于线段树是基本技能，所以不再此过多解释。
树链剖分操作如下
操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和
还有几个概念：重儿子，轻儿子，重链，轻链。
众所周知，以每一个节点为根节点下所成的树（语文技能崩溃）都有一个大小（节点的数量）
如果有一个儿子体型（节点数）在所有兄弟姐妹中最大，那么这个儿子就是这个节点的重儿子；
其他的儿子都是轻儿子。
重边就是每两个重儿子之间的边（手拉手，我们都是重儿子）；轻边就是剩下的；
重链就是相邻的每个重边连起来的链，包括一条端点重儿子和轻儿子之间的边，也就是所有重链以一个轻儿子开始；
看完定义该干事了！！！
首先，处理dep[],fa[],siz[],son[]
void dfs1(int u,int fa)
{
f[u]=fa;//记录u节点的父亲
siz[u]=1;//子树大小，包括他自己
dep[u]=dep[fa]+1;//深度
for(int p=last[u];p;p=pre[p])
{
int v=other[p];
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;//记录重儿子
}
}
second 新编，赋值，找头，先重再轻
因为先处理重儿子就会让重儿子之间的编号是连续的。
void dfs2(int u,int tp)
{
id[u]=++cnt;//重新编号
top[u]=tp;//这个点所在链的顶端
b[cnt]=a[u];//新编号赋值
if(!son[u]) return ;//no son
dfs2(son[u],tp);
for(int p=last[u];p;p=pre[p])
{
int v=other[p];
if(v==son[u]||v==f[u]) continue;
dfs2(v,v);//对于每一个轻儿子都有一条从它自己开始的链
}
}
third 套用线段树。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100050;
int n,m,s,mo,a[maxn];
int pre[maxn*2],other[maxn*2],last[maxn],l;
int f[maxn],siz[maxn],dep[maxn],son[maxn];
int id[maxn],cnt,top[maxn],b[maxn];
void add(int x,int y)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
}
//下面是线段树
struct tree
{
int l,r;
int sum,lazy;
}t[4*maxn];//四倍，前人的经验
void build(int x,int l,int r)//建树
{
t[x].l=l;t[x].r=r;
if(l==r)
{
t[x].sum=b[l];
return ;
}
int mid=(l+r)>>1;
build(2*x,l,mid);
build(2*x+1,mid+1,r);
t[x].sum=(t[2*x].sum+t[2*x+1].sum)%mo;
}
void update(int x)//更新懒标签
{
t[2*x].sum+=((t[2*x].r-t[2*x].l+1)*t[x].lazy)%mo;
t[2*x+1].sum+=((t[2*x+1].r-t[2*x+1].l+1)*t[x].lazy)%mo;
t[2*x].lazy+=t[x].lazy;t[2*x].lazy%=mo;
t[2*x+1].lazy+=t[x].lazy;t[2*x+1].lazy%=mo;
t[x].lazy=0;
}
void change(int x,int l,int r,int z)//改变值
{
if(t[x].l==l&&t[x].r==r)
{
t[x].sum+=(t[x].r-t[x].l+1)*z;
t[x].lazy+=z;
return ;
}
if(t[x].lazy) update(x);
int mid=(t[x].l+t[x].r)>>1;
if(r<=mid) change(2*x,l,r,z);
else if(l>mid) change(2*x+1,l,r,z);
else
{
change(2*x,l,mid,z);
change(2*x+1,mid+1,r,z);
}
t[x].sum=(t[2*x].sum+t[2*x+1].sum)%mo;
}
int query(int x,int l,int r)//查询区间和
{
if(t[x].l==l&&t[x].r==r)
{
return t[x].sum;
}
if(t[x].lazy) update(x);
int mid=(t[x].l+t[x].r)>>1;
if(r<=mid) return query(2*x,l,r);
else if(l>mid) return query(2*x+1,l,r);
else
{
return query(2*x,l,mid)+query(2*x+1,mid+1,r);
}
}
//上面是线段树
void dfs1(int u,int fa)
{
f[u]=fa;//记录u节点的父亲
siz[u]=1;//子树大小，包括他自己
dep[u]=dep[fa]+1;//深度
for(int p=last[u];p;p=pre[p])
{
int v=other[p];
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;//记录重儿子
}
}
void dfs2(int u,int tp)
{
id[u]=++cnt;//重新编号
top[u]=tp;//这个点所在链的顶端
b[cnt]=a[u];//新编号赋值
if(!son[u]) return ;//no son
dfs2(son[u],tp);
for(int p=last[u];p;p=pre[p])
{
int v=other[p];
if(v==son[u]||v==f[u]) continue;
dfs2(v,v);//对于每一个轻儿子都有一条从它自己开始的链
}
}
void tchange(int x,int y,int z)
{
z%=mo;
while(top[x]!=top[y])//如果不在一条链上
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//从深度小的来
change(1,id[top[x]],id[x],z);//一条链上加上z
x=f[top[x]];
}//到一条链上之后跳出
if(dep[x]>dep[y]) swap(x,y);//找到深度浅的那个
change(1,id[x],id[y],z);//最后一条链加z
}
int tcha(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(1,id[top[x]],id[x]);
ans%=mo;
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(1,id[x],id[y]);
ans%=mo;
return ans;
}
void changeson(int x,int z)
{
change(1,id[x],id[x]+siz[x]-1,z);//新编节点中每个节点和儿子们是连续的多么重要
}
int chason(int x)
{
return query(1,id[x],id[x]+siz[x]-1);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&mo);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs1(s,0);
dfs2(s,s);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int op,x,y,z;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&x,&y,&z);
tchange(x,y,z);// 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
}
else if(op==2)
{
scanf("%d%d",&x,&y);
printf("%d
",tcha(x,y)%mo);// 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
}
else if(op==3)
{
scanf("%d%d",&x,&z);// 3 x z 表示将以x为根节点的子树内所有节点值都加上z
changeson(x,z);
}
else if(op==4)
{
scanf("%d",&x);
printf("%d
",chason(x)%mo);// 4 x 表示求以x为根节点的子树内所有节点值之和
}
}
return 0;
}
刚学会，理解还是不太到位，欢迎指正。
温馨提示（放在最后坑你们）：每个加减计算都要取模。。。。。。