树剖学习笔记
树链剖分是一种将树剖分成若干条链，维护树上信息的方式。
树链剖分大多指的是重链剖分，还有长链剖分和实链剖分。
我们先给出几个定义：
- 重儿子：子树大小最大的儿子。
- 轻儿子：除了重儿子以外的其他儿子。
- 重边：连接重儿子的那一条边。
- 轻边：连接轻儿子的那一条边。
- 重链：将连续的重边相连成为的一条链。
重链的一些性质：
-
一个节点属于且仅属于一条重链。
-
任意两个点的路径中的重链数量是小于 \(\log n\) 级别的。
证明：相邻的两条重链肯定有一条轻边，经过这一条轻边，子树大小小于原来子树大小的一半，所以最多经过 \(\log n\) 条轻边，即最多有 \(\log n\) 条重链。
对于重链的实现，其实很简单，但是一般来说会让同一条重链的 dfs 序是连续的，所以 dfs 先遍历重儿子会更好一点。
实现：
void dfs2(int u,int t) {L[u]=++cnt;a[cnt]=u;top[u]=t;if(son[u])dfs2(son[u],t);for(auto tmp:e[u]) {int v=tmp.x,w=tmp.y,id=tmp.z;if(v==fa[u] || v== son[u])continue;dfs2(v,v);}R[u]=cnt;
}
重链剖分可以实现 LCA， 常数较小，会比倍增快一点。（但其实差不多）
具体就是将这两个点的重链顶深度较大的跳到重链顶的 father。直到两个点的重链顶相同，这时深度小的就是深度大的祖先。深度小的就是 LCA。
int LCA(int x,int y){while(top[x] !=top[y]){if(dep[top[x]] <dep[top[y]])swap(x,y);x=fa[top[x]];}return dep[x]<dep[y]?x:y;
}
我们可以使用树剖的重链 dfs 序连续的性质，来结合数据结构动态解决一些链上的修改问题。
例题 ：[P1505 国家集训队] 旅游 - 洛谷 (luogu.com.cn)
这里的维护最大值最小值和区间和比较好写，注意一下区间取反的操作对最大值和最小值的改变，整体的代码和 LCA 大同小异。
核心代码如下：
int solve1(int u,int v,int z){int res=0;if(z==1)res=0;if(z==2)res=-inf;if(z==3)res= inf;while(top[u]!=top[v]){if(dep[top[u]] < dep[top[v]]) swap(u,v);if(z==1) res+=seg.query(1,1,n,L[top[u]],L[u]).sum;if(z==2) tomax(res,seg.query(1,1,n,L[top[u]],L[u]).mx );if(z==3) tomin(res,seg.query(1,1,n,L[top[u]],L[u]).mi );u=fa[top[u]];//cout<<u<<" "<<v<<endl;}if(u==v)return res;if(dep[u] <dep[v])swap(u,v);if(z==1) res+=seg.query(1,1,n,L[v]+1,L[u]).sum;if(z==2) tomax(res,seg.query(1,1,n,L[v]+1,L[u]).mx );if(z==3) tomin(res,seg.query(1,1,n,L[v]+1,L[u]).mi );return res;
}void solve2(int u,int v){while(top[u]!=top[v]){if(dep[top[u]] < dep[top[v]]) swap(u,v);seg.change2(1,1,n,L[top[u]],L[u]); u=fa[top[u]];}if(dep[u]<dep[v])swap(u,v);seg.change2(1,1,n,L[v]+1,L[u]);
}
用树链剖分来实现基本上都是 \(O(n \log^2n)\) 的。树剖的常数比较小，所以有些题目是可以卡过去的。
当然，树剖也可以非常有效的实现 DDP，时间复杂度为 \(O(n k^3\log^2 n)\) \(k\) 为转移矩阵大小。
这里的转移矩阵需要具体题目具体分析。
大概的实现过程是先求出去掉重儿子的答案，这样可以去掉树上问题特有的求子树的和或最大值。
通过这个去掉重儿子的答案和重儿子的 dp 值，通过建立转移矩阵来转移。
修改只需要更改转移矩阵，并更新线段树即可。
其实主要可能是去掉重儿子的答案脑子可能转不过来，矩阵有点构造，原来的 dp 式子有点难推。
例题：P4719 【模板】动态 DP - 洛谷 (luogu.com.cn)
一个以树上最大独立集为模板做的一个经典的 ddp 。
我们知道 \(dp_{i,0/1}\) 表示这个点选或不选子树中最大的答案。
\(dp_{i,0} = \sum_ \max(dp _{j,1},dp_{j,0})\)
$dp_{i,1}=a_i+\sum dp_{j,0} $
考虑 ddp，设 \(f_{i,0/1}\) 为去掉重儿子的答案。
可得转移：
\(dp_{i,0}=f_{i,0} + \max(dp_{son_i,0},dp_{son_i,1})\)
\(dp_{i,1}=f_{i,1}+a_i + dp_{son_i,0}\)
稍微转化一下：
\(dp_{i,0}=\max(dp_{son_i,0}+f_{i,0},dp_{son_i,1}+f_{i,0})\)
\(dp_{i,1}=\max(dp_{son_i,0}+a_i+f_{i,1},dp_{son_i,0}-\inf)\)
（后面的 \(\inf\) 是不能转移的意思。）
可以写出矩阵乘法的形式：
但是这个转移是从下往上的，我们的树剖 dfs 序是从上往下的，这不行。
我们调个位置。
这样的话我们的转移和求解的顺序是一样的了。
当然，对于每次更改，就需要对轻链的矩阵进行更改，刚好我们使用了树链剖分。只有一条重链的最低端需要更改，其他的转移矩阵不需要更改。最后只需要把包含根的这一条重链的区间答案求出来就是答案了，细节可以看一下代码。
#include<bits/stdc++.h>
using namespace std;
const int N=1E5+5,inf=1e9;
int n,a[N],m;
int dfn[N],id[N],dep[N],siz[N],son[N],top[N],fa[N],cnt,bot[N];
int f[N][2];
vector<int>e[N];
void tomax(int &x,int y){if(x<y)x=y;
}
struct Mat{int c[2][2];Mat(){memset(c,-0x3f,sizeof c);}Mat operator *(const Mat &a)const {Mat res;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)tomax(res.c[i][j],c[i][k]+a.c[k][j]);return res;}
}val[N];
struct SEG{#define ls p<<1#define rs p<<1|1#define mid (l+r>>1)Mat c[N<<2];void pushup(int p){c[p]=c[ls]*c[rs];}void change(int p,int l,int r,int x){if(l==r)return c[p]=val[id[l]],void ();if(x<=mid)change(ls,l,mid,x);else change(rs,mid+1,r,x);pushup(p);}Mat query(int p,int l,int r,int L,int R){if(L<=l && r<=R)return c[p];if(L<=mid && R >mid)return query(ls,l,mid,L,R) * query(rs,mid+1,r,L,R);if(L<=mid) return query(ls,l,mid,L,R);return query(rs,mid+1,r,L,R);}void build(int p,int l,int r){if(l==r){//cout<<l<<" "<<val[id[l]].c[1][0]<<endl;return c[p]=val[id[l]],void ();}build(ls,l,mid),build(rs,mid+1,r);pushup(p);}
}seg;
void dfs1(int u,int F){dep[u]=dep[F]+1;fa[u]=F;siz[u]=1;son[u]=0;for(int v:e[u]){if(v==F)continue;dfs1(v,u);siz[u]+=siz[v];if(!son[u] || siz[v] > siz[son[u]])son[u]=v;}
}
void dfs2(int u,int t){id[dfn[u]=++cnt]=u;top[u]=t;bot[t]=max(bot[t],cnt);f[u][0]=0;f[u][1]=a[u];val[u].c[0][0]=val[u].c[0][1]=0;val[u].c[1][0]=a[u];if(son[u]){dfs2(son[u],t);f[u][0]+=max(f[son[u]][0],f[son[u]][1]);f[u][1]+=f[son[u]][0];}for(int v:e[u]){if(v==fa[u] || son[u]==v)continue;dfs2(v,v);f[u][0]+=max(f[v][0],f[v][1]);f[u][1]+=f[v][0];val[u].c[0][0]+=max(f[v][0],f[v][1]);val[u].c[0][1]+=max(f[v][0],f[v][1]);val[u].c[1][0]+=f[v][0];}
}
void solve(int u,int w){val[u].c[1][0]+=w-a[u];a[u]=w;while(u){auto tmp1=seg.query(1,1,n,dfn[top[u]],bot[top[u]]);seg.change(1,1,n,dfn[u]);auto tmp2=seg.query(1,1,n,dfn[top[u]],bot[top[u]]);u=fa[top[u]];val[u].c[0][0]+=max(tmp2.c[1][0],tmp2.c[0][0])-max(tmp1.c[1][0],tmp1.c[0][0]);val[u].c[0][1]= val[u].c[0][0];val[u].c[1][0]+=tmp2.c[0][0]-tmp1.c[0][0];}
}
signed main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);e[u].push_back(v);e[v].push_back(u);}dfs1(1,0);dfs2(1,1);//for(int i=1;i<=n;i++){// cout<<val[id[i]].c[0][0]<<" "<<val[id[i]].c[1][0]<<" "<<val[id[i]].c[0][1]<<endl;//}seg.build(1,1,n);//cout<<seg.query(1,1,n,dfn[1],bot[1]).c[1][0]<<" "<<seg.query(1,1,n,dfn[1],bot[1]).c[0][0]<<endl; for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);solve(x,y);auto tmp=seg.query(1,1,n,dfn[1],bot[1]);cout<<max(tmp.c[0][0],tmp.c[1][0])<<endl;}return 0;
}