树链剖分首先要学点预备知识LCA，树形DP，DFS序
emmmmmm..... 还要会链式前向星，线段树
树链剖分
目录
概念
dfs1()
这个dfs要处理的几个事情
inline void dfs1(int x,int fa,int dep){
deep[x] = dep;
father[x] = fa;
size[x] = 1;
int maxson = -1;
for(register int i = begin[x];i;i = next[i]){
int y = to[i];
if(y == fa)continue;
dfs1(y,x,dep+1);
size[x] += size[y];
if(size[y] > maxson)son[x] = y,maxson = size[y];
}
}
dfs2()
这个dfs要处理的事情
顺序：先处理重儿子再处理轻儿子，给大家模拟一下
inline void dfs2(int x,int topf){
id[x] = ++cnt;
a[cnt] = w[x];
top[x] = topf;
if(!son[x])return;
dfs2(son[x],topf);
for(register int i = begin[x];i;i = next[i]){
int y = to[i];
if(y == father[x] || y == son[x])continue;
dfs2(y,y);
}
}
处理问题
1、当我们要处理任意两点间路径时：
设所在链顶端的深度更深的那个点为x点
不停执行这两个步骤，直到两个点处于一条链上，这时再加上此时两个点的区间和即可
这时我们注意到，我们所要处理的所有区间均为连续编号(新编号)，于是想到线段树，用线段树处理连续编号区间和
每次查询时间复杂度为O(log2n)
inline int query_range(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,id[top[x]],id[x]);
ans += res;
ans %= mod;
x = father[top[x]];
}
if(deep[x] > deep[y])swap(x,y);
res = 0;
query(1,1,n,id[x],id[y]);
ans += res;
return ans%mod;
}
2、处理一点及其子树的点权和：
想到记录了每个非叶子节点的子树大小(含它自己)，并且每个子树的新编号都是连续的
于是直接线段树区间查询即可
时间复杂度为O(logn)
inline int query_son(int x){
res = 0;
query(1,1,n,id[x],id[x]+size[x]-1);
return res;
}
区间修改就和区间查询一样的
inline void update_range(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,id[top[x]],id[x],k);
x = father[top[x]];
}
if(deep[x] > deep[y])swap(x,y);
update(1,1,n,id[x],id[y],k);
}
建树
既然前面说到要用线段树，那么按题意建树就可以啦！
AC代码
#include<bits/stdc++.h>
using namespace std;
#define Temp template<typename T>
#define mid ((l+r)>>1)
#define left_son root<<1,l,mid
#define right_son root<<1|1,mid+1,r
#define len (r-l+1)
const int maxn = 2e5+5;
Temp inline void read(T &x){
x=0;T w=1,ch=getchar();
while(!isdigit(ch)&&ch!=‘-‘)ch=getchar();
if(ch==‘-‘)w=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^‘0‘),ch=getchar();
x=x*w;
}
int n,m,r,mod;
int e,begin[maxn],next[maxn],to[maxn],w[maxn],a[maxn];
int tree[maxn<<2],lazy[maxn<<2];
int son[maxn],id[maxn],father[maxn],cnt,deep[maxn],size[maxn],top[maxn];
int res;
inline void add(int x,int y){
to[++e] = y;
next[e] = begin[x];
begin[x] = e;
}
inline void pushdown(int root,int pos){
lazy[root<<1] += lazy[root];
lazy[root<<1|1] += lazy[root];
tree[root<<1] += lazy[root]*(pos-(pos>>1));
tree[root<<1|1] += lazy[root]*(pos>>1);
tree[root<<1] %= mod;
tree[root<<1|1] %= mod;
lazy[root] = 0;
}
inline void pushup(int root){
tree[root]=(tree[root<<1]+tree[root<<1|1])%mod;
}
inline void build(int root,int l,int r){
if(l == r){
tree[root] = a[l];
if(tree[root] > mod)tree[root] %= mod;
return;
}
build(left_son);
build(right_son);
pushup(root);
}
inline void query(int root,int l,int r,int al,int ar){
if(al <= l && r <= ar){
res += tree[root];
res %= mod;
return;
}
else{
if(lazy[root])pushdown(root,len);
if(al <= mid)query(left_son,al,ar);
if(ar > mid)query(right_son,al,ar);
}
}
inline void update(int root,int l,int r,int al,int ar,int k){
if(al <= l && r <= ar){
lazy[root] += k;
tree[root] += k*len;
}
else{
if(lazy[root])pushdown(root,len);
if(al <= mid)update(left_son,al,ar,k);
if(ar > mid)update(right_son,al,ar,k);
pushup(root);
}
}
inline int query_range(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,id[top[x]],id[x]);
ans += res;
ans %= mod;
x = father[top[x]];
}
if(deep[x] > deep[y])swap(x,y);
res = 0;
query(1,1,n,id[x],id[y]);
ans += res;
return ans%mod;
}
inline void update_range(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,id[top[x]],id[x],k);
x = father[top[x]];
}
if(deep[x] > deep[y])swap(x,y);
update(1,1,n,id[x],id[y],k);
}
inline int query_son(int x){
res = 0;
query(1,1,n,id[x],id[x]+size[x]-1);
return res;
}
inline void update_son(int x,int k){
update(1,1,n,id[x],id[x]+size[x]-1,k);
}
inline void dfs1(int x,int fa,int dep){
deep[x] = dep;
father[x] = fa;
size[x] = 1;
int maxson = -1;
for(register int i = begin[x];i;i = next[i]){
int y = to[i];
if(y == fa)continue;
dfs1(y,x,dep+1);
size[x] += size[y];
if(size[y] > maxson)son[x] = y,maxson = size[y];
}
}
inline void dfs2(int x,int topf){
id[x] = ++cnt;
a[cnt] = w[x];
top[x] = topf;
if(!son[x])return;
dfs2(son[x],topf);
for(register int i = begin[x];i;i = next[i]){
int y = to[i];
if(y == father[x] || y == son[x])continue;
dfs2(y,y);
}
}
int main(){
read(n);
read(m);
read(r);
read(mod);
for(register int i = 1;i <= n;i++)read(w[i]);
for(register int i = 1,x,y;i <n;i++){
read(x);
read(y);
add(x,y);
add(y,x);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,n);
while(m--){
int k,x,y,z;
read(k);
if(k == 1){
read(x);
read(y);
read(z);
update_range(x,y,z);
}
if(k == 2){
read(x);
read(y);
printf("%d\n",query_range(x,y));
}
if(k == 3){
read(x);
read(y);
update_son(x,y);
}
if(k == 4){
read(x);
printf("%d\n",query_son(x));
}
}
return 0;
}
完事~~~
搞定收工！！！
原文：https://www.cnblogs.com/wangyifan124/p/10293868.html