看原题戳这儿
如题，肯定是树链剖分的题。
零、写在前面
前置知识：链式前向星，树，dfs序，LCA，树形dp，线段树
如果这些没学好的话，(emm)
好了，进入正文
一、树链剖分是啥
顾名思义，就是将一棵树剖分成几条链，把树形变为线性，以减少处理难度，的一系列骚逼操作。
一（yì）点点概念
- 重儿子：对于每一个非叶子节点，它的儿子中儿子数量最多的那一个儿子 为该节点的重儿子
- 轻儿子：对于每一个非叶子节点，它的儿子中不是重儿子 的儿子。
- 叶子节点既没有重儿子也没有轻儿子（因为它没有儿子······）
- 重边：连接任意两个重儿子的边叫做重边
- 轻边：不是重边的边叫做轻边
- 重链：相邻重边连起来的连接一条重儿子的链叫重链
- 对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链
- 每一条重链以轻儿子为起点
二、这道题咋做（代码如何实现）
0.审题
题目描述
如题，已知一棵包含 (N) 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
操作 (1)： 格式：$ 1 x y z $ 表示将树从 (x) 到 (y) 结点最短路径上所有节点的值都加上 z。
操作 (2)： 格式：$ 2 x y $ 表示求树从 (x) 到 (y) 结点最短路径上所有节点的值之和。
操作 (3)： 格式：$ 3 x z$ 表示将以 (x) 为根节点的子树内所有节点值都加上 (z)。
操作 (4)： 格式：$ 4 x $表示求以 (x) 为根节点的子树内所有节点值之和
数据规模
对于 (30\%) 的数据：$ 1 leq N leq 10,1 leq M leq 10$
对于 (70\%)的数据： (1 leq N leq {10}^3, 1 leq M leq {10}^3)
对于 (100\%) 的数据： $1le N leq {10}^5, 1le M leq {10}^5,1le Rle N,1le P le 2^{31}-1 $
乍一看题，N和M都是({10}^5)，肯定(O({n}^2))是不行的，要用(O(n))或(O(nlogn))的算法，于是便想到用树剖（实际上是因为这是板子）。
1.预处理
要用两个(dfs())。
为什么不能合并？因为(dfs2())要用(dfs1())推出
dfs1()
这个dfs要处理这四件事情：
-
标记每个点的深度dep[ ]
-
标记每个点的父亲fa[ ]
-
标记每个非叶子节点的子树大小(含它自己)
-
标记每个非叶子节点的重儿子编号son[ ]
inline void dfs1(int u,int f,int deep)//x表示当前节点，f表示当前节点的父亲，deep表示当前节点的深度
{
dep[u]=deep;//处理深度
fa[u]=f;//处理父亲
siz[u]=1;//先标记
int maxson=-1;//最大的儿子
for(int i=head[u];i!=0;i=e[i].nxt)
{
int v=e[i].to;
if(v==f)continue;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>maxson) son[u]=v,maxson=siz[v];//判断是否是重儿子
}
}
dfs2()
这个dfs要处理这四件事情：
-
标记每个点的新编号
-
赋值每个点的初始值到新编号上
-
处理每个点所在链的顶端
-
处理每条链
顺序：先处理重儿子再处理轻儿子
inline void dfs2(int x,int topf)//x表示当前节点，topf当前节点所在链的最顶端的节点
{
id[x]=++cnt；//重新编号
wt[cnt]=w[x]；//重新赋值
top[x]=topf;//处理链的顶端
if(!son[x]) return;//如果没有儿子就返回
dfs2(son[x],topf);//先处理重儿子
for(int i=head[x];i!=0;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa[x]||v==son[x])continue;//判定是否重复
dfs2(v,v);//每一个轻儿子都有一条以他为起始的链
}
}
建树
（其实就和线段树一样）
前面说到要用线段树，那么按题意建树就可以了。
不过需要注意的是，建树这一步要放在处理问题之前，不然······。
2.正式的算法部分
前面说到dfs2的顺序是先处理重儿子再处理轻儿子,为什么呢？
我们来模拟一下：
-
因为顺序是先重再轻，所以每一条重链的新编号是连续的
-
因为是dfs，所以每一个子树的新编号也是连续的
现在回顾一下我们要处理的问题
-
处理任意两点间路径上的点权和
-
处理一点及其子树的点权和
-
修改任意两点间路径上的点权
-
修改一点及其子树的点权
1、处理任意两点间路径时： 设所在链顶端的深度更深的那个点为x点
方法：
-
ans加上x点到x所在链顶端 这一段区间的点权和
-
把x跳到x所在链顶端的那个点的上面一个点
不停执行这两个步骤，直到两个点处于一条链上，这时再加上此时两个点的区间和即可
这时我们注意到，我们所要处理的所有区间均为 连续编号(新编号)（这就是为什么要先处理重儿子） ，于是想到线段树，用线段树处理连续编号区间和（为什么代码这么长？就因为这）
每次查询时间复杂度为(O(log^2n))，不错。
inline int qRange(int x,int y)
{
int ans=0;
while(top[x]!=top[y])//若两个点不在一条链上
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//把链的顶端更深的放在前面
res=0;
query(1,1,a,id[top[x]],id[x]);//使用线段树将ans加上x点到x所在链顶端，这一段区间的点权和
ans+=res;
ans%=mod;
x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点，继续循环
}
//两个点终于在一条链上了
if(dep[x]>dep[y]) swap(x,y);//把链的顶端更深的放在前面
res=0;
query(1,1,a,id[x],id[y]);//再求一次
ans+=res;
return ans%mod;
}
2、处理一点及其子树的点权和：
想到记录了每个非叶子节点的子树大小(含它自己)，并且每个子树的新编号都是连续的（先处理重儿子是不是好处多多？），然后直接线段树区间查询就行啦！！！时间复杂度为$ O(logn) $，很好
inline int qSon(int x)
{
res=0;
query(1,1,a,id[x],id[x]+siz[x]-1);//子树区间右端点id[x]+siz[x]-1
return res;
}
当然，区间修改是和区间查询一样的
inline void updRange(int x,int y,int k)
{
k%=mod;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,a,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,1,a,id[x],id[y],k);
}
inline void updSon(int x,int k)
{
update(1,1,a,id[x],id[x]+siz[x]-1,k);
}
三.代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct node{
int to,nxt;
} e[500001];
int a,b,r,mod,res;
int ecnt,head[100001],w[100001],wt[100001];
int tree[2000001],laz[2000001];
int son[100001],id[100001],fa[100001],cnt,dep[100001],siz[100001],top[100001];
inline void add(int x,int y)
{
e[++ecnt].to=y;
e[ecnt].nxt=head[x];
head[x]=ecnt;
}
//--------------------------------------
inline void pushdown(int p,int lenn)
{
laz[p<<1]+=laz[p];
laz[p<<1|1]+=laz[p];
tree[p<<1]+=laz[p]*(lenn-(lenn>>1));
tree[p<<1|1]+=laz[p]*(lenn>>1);
tree[p<<1]%=mod;
tree[p<<1|1]%=mod;
laz[p]=0;
}
inline void build(int p,int l,int r)
{
int mid=(l+r)>>1;
if(l==r)
{
tree[p]=wt[l];
if(tree[p]>mod)tree[p]%=mod;
return;
}
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tree[p]=(tree[p<<1]+tree[p<<1|1])%mod;
}
inline void query(int p,int l,int r,int L,int R)
{
int mid=(l+r)>>1;
if(L<=l&&r<=R)
{
res+=tree[p];
res%=mod;
return;
}
else
{
if(laz[p]) pushdown(p,r-l+1);
if(L<=mid) query(p<<1,l,mid,L,R);
if(R>mid) query(p<<1|1,mid+1,r,L,R);
}
}
inline void update(int p,int l,int r,int L,int R,int k)
{
int mid=(l+r)>>1;
if(L<=l&&r<=R)
{
laz[p]+=k;
tree[p]+=k*(r-l+1);
}
else
{
if(laz[p]) pushdown(p,r-l+1);
if(L<=mid) update(p<<1,l,mid,L,R,k);
if(R>mid) update(p<<1|1,mid+1,r,L,R,k);
tree[p]=(tree[p<<1]+tree[p<<1|1])%mod;
}
}
//---------------------------------
inline int qRange(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
res=0;
query(1,1,a,id[top[x]],id[x]);
ans+=res;
ans%=mod;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=0;
query(1,1,a,id[x],id[y]);
ans+=res;
return ans%mod;
}
inline void updRange(int x,int y,int k)
{
k%=mod;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,a,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,1,a,id[x],id[y],k);
}
inline int qSon(int x)
{
res=0;
query(1,1,a,id[x],id[x]+siz[x]-1);
return res;
}
inline void updSon(int x,int k)
{
update(1,1,a,id[x],id[x]+siz[x]-1,k);
}
inline void dfs1(int u,int f,int deep)
{
dep[u]=deep;
fa[u]=f;
siz[u]=1;
int maxson=-1;
for(int i=head[u];i!=0;i=e[i].nxt)
{
int v=e[i].to;
if(v==f)continue;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>maxson) son[u]=v,maxson=siz[v];
}
}
inline void dfs2(int x,int topf)
{
id[x]=++cnt,wt[cnt]=w[x],top[x]=topf;
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=head[x];i!=0;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa[x]||v==son[x])continue;
dfs2(v,v);
}
}
int main()
{
freopen("a1.in","r",stdin);
scanf("%d%d%d%d",&a,&b,&r,&mod);
for(int i=1;i<=a;++i) scanf("%d",w+i);
cout<<1<<endl;
for(int i=1;i<a;++i)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,a);
for(int i=1;i<=b;++i)
{
int k,x,y,z;
scanf("%d",&k);
if(k==1)
{
scanf("%d%d%d",&x,&y,&z);
updRange(x,y,z);
}
else if(k==2)
{
scanf("%d%d",&x,&y);
printf("%d
",qRange(x,y));
}
else if(k==3)
{
scanf("%d%d",&x,&y);
updSon(x,y);
}
else
{
scanf("%d",&x);
printf("%d
",qSon(x));
}
}
return 0;
}
完美撒花！！！
四.幕后
新人第一篇题解。手打2h+，制作不易，点个赞再走吧。