前言
这几天疯狂地在补树链剖分的坑，也刷了几道题，这里做个小结。
树链剖分
树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。
具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。（摘自Oi wiki）。
常见的树链剖分主要是重链剖分。
即定义某一节点的的子节点中子树大小最大的一点为它的重儿子，在dfs遍历时优先遍历。连接这两个点的边成为重边，若干重边相连构成了一条重链。
值得注意的是，因为重儿子和重边是对每一节点都有定义的，所以整棵树是被分成了若干条重链的，每一个节点也都属于且仅属于一条重链。
如下图。(依旧摘自Oi wiki)
在上图中，我们可以发现一条重链上的dfs序是连续的，这就启示我们可以用一些维护序列的数据结构来维护这棵树。那用什么呢.（小声bb：肯定不是线段树）
线段树是维护序列信息的老大哥了，所以它来了。（于是你的树剖代码动辄100+ 200+，麻了）
我们可以十分便利地利用线段树来维护许多树上的信息，比如说路径上的最大值，以及累加和。
实现
实现树链剖分一般需要7个数组。
s z e [ x ] sze[x] sze[x]：以 x x x为根的子树大小。
d e p [ x ] dep[x] dep[x]： x x x节点的深度。
s o n [ x ] son[x] son[x]： x x x的重儿子。
f a [ x ] fa[x] fa[x]： x x x的父节点。
t o p [ x ] top[x] top[x]： x x x所处重链的链顶。
d f n [ x ] dfn[x] dfn[x]： x x x的 d f s dfs dfs序。
r n k [ x ] rnk[x] rnk[x]: d f s dfs dfs序为 x x x的点的编号。有 r n k [ d f n [ x ] ] = x rnk[dfn[x]]=x rnk[dfn[x]]=x 比较绕。
而在处理有关子树的问题时，我们通常需要额外记录一个 e n en en数组表示以 x x x为根的子树的结束，利用子树内的 d f s dfs dfs序同样连续来维护信息。
下面给出本蒟蒻常用的模板。（前向星存图）
struct edge{
int y,nxt;
}Edge[N<<1];//前向星存图
int Link[N],sze[N],fa[N],dep[N],son[N],len=0,dfn[N],rnk[N],top[N],tot=0,n,m,v[N];
void insert(int x,int y) {
Edge[++len]={y,Link[x]};
Link[x]=len;
}//加边函数
void dfs1(int now,int fath) {//求出sze，fa，dep，son
dep[now]=dep[fath]+1;sze[now]=1;fa[now]=fath;son[now]=-1;//对当前节点的处理
for(int i=Link[now];i;i=Edge[i].nxt) {
int y=Edge[i].y;
if(dep[y]) continue;
dfs1(y,now);
sze[now]+=sze[y];//加上它儿子的子树大小
if(son[now]==-1||sze[y]>sze[son[now]]) son[now]=y;//更新重儿子
}
}
void dfs2(int now,int ttp) {//求出top，dfn，rnk。ttp表示链顶
top[now]=ttp;dfn[now]=++tot;rnk[tot]=now;
if(son[now]==-1) return ;//没有重儿子，说明是叶节点。return
dfs2(son[now],ttp);//优先遍历重儿子
for(int i=Link[now];i;i=Edge[i].nxt) {
int y=Edge[i].y;
if(y==fa[now]||y==son[now]) continue;
dfs2(y,y);//对于轻儿子来说，它是新一条重链的链顶
}
}
时间复杂度
可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。
因此，对于树上的任意一条路径，把它拆分成从 l c a lca lca 分别向两边往下走，分别最多走 l o g n logn logn 次，因此，树上的每条路径都可以被拆分成不超过 l o g n logn logn 条重链。
（还是Oi wiki）
所以其时间复杂度是 n l o g 2 n nlog^2n nlog2n的~~（本蒟蒻不会，记住就好）~~
例题
lg P3379 【模板】最近公共祖先（LCA）
题面描述
给定n个点的树(1是根)，m次询问，每次询问两点的LCA;
做法
一个做法多样的板子题。可以倍增，当然也可以树剖求。只需要对于查询的两个节点，在其 t o p top top不相等的时候，每次让节点深度大的那个向上跳即可。
当二者处于同一重链中时，深度较小的那个即为 l c a lca lca。
核心代码如下
int lca(int x,int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]>dep[top[y]] ) x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]>dep[y]?y:x;
}
请注意这个 w h i l e while while循环，几乎所有路径上操作都需要用到它，务必按上面的图手推一遍，确保深刻理解。
HDOJ2586 how far away?(lg不知道哪道题)
题面描述
给出 个点的一棵树，多次询问两点之间的最短距离。
做法
本质和上一道题并无区别，只需在 d f s 1 dfs1 dfs1中计算出每个节点到根节点的距离 d i s dis dis,最后答案即为 d i s [ x ] + d i s [ y ] − 2 ∗ d i s [ l c a ( x , y ) ] dis[x]+dis[y]-2*dis[lca(x,y)] dis[x]+dis[y]−2∗dis[lca(x,y)]。
不再提供代码 （因为我不是用树剖写的）
lg P2590 [ZJOI2008]树的统计
题面描述
一树上有 n n n个节点，编号分别为 1 1 1 到 n n n，每个节点都有一个权值 。我们将以下面的形式来要求你对这棵树完成一些操作：
C H A N G E CHANGE CHANGE u u u t t t ：把节点 u u u权值改为 t t t；
Q M A X QMAX QMAX u u u v v v ：询问点 u u u到点 v v v路径上的节点的最大权值；
Q S U M QSUM QSUM u u u v v v ：询问点 u u u到点 v v v路径上的节点的权值和。
注意：从点 u u u到点 v v v路径上的节点包括 u u u和 v v v 本身。
做法
很板子的一个板子题。只需要线段树维护即可。
struct tree{//线段树维护的是dfs序上的内容
int l,r,sum,mx;
}t[N<<2];
void pushup(int p) {
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}
void build(int p,int l,int r) {
t[p].l=l,t[p].r=r;
if(l==r) {
t[p].sum=t[p].mx=v[rnk[l]];//该dfs序所对应的节点的权值
return ;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void change(int p,int x,int v) {
if(t[p].l==x&&t[p].r==x) {
t[p].mx=t[p].sum=v;
return ;
}
int mid=t[p].l+t[p].r>>1;
if(x<=mid) change(p<<1,x,v);
else change(p<<1|1,x,v);
pushup(p);
}
int ask_sum(int p,int l,int r) {
if(t[p].l>=l&&t[p].r<=r) {
return t[p].sum;
}
int mid=t[p].l+t[p].r>>1,summ=0;
if(l<=mid) summ+=ask_sum(p<<1,l,r);
if(mid<r) summ+=ask_sum(p<<1|1,l,r);
return summ;
}
int ask_max(int p,int l,int r) {
if(t[p].l>=l&&t[p].r<=r) return t[p].mx;
int mid=t[p].l+t[p].r>>1,maxx=-1e9-7;
if(l<=mid) maxx=max(maxx,ask_max(p<<1,l,r));
if(mid<r) maxx=max(maxx,ask_max(p<<1|1,l,r));
return maxx;
}
void Q_MAX(int x,int y) {
int maxx=-1e9-7;
while(top[x]!=top[y]) {//两个节点不在同一条链上时，深度大的向上跳
if(dep[top[x]]>dep[top[y]]) {
maxx=max(maxx,ask_max(1,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
else {
maxx=max(maxx,ask_max(1,dfn[top[y]],dfn[y]));
y=fa[top[y]];
}
}
maxx=max(maxx,ask_max(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])));//在同一条链上的处理
printf("%d\n",maxx);
}
void Q_SUM(int x,int y) {
int ssum=0;
while(top[x]!=top[y]) {
if(dep[top[x]]>dep[top[y]] ) {
ssum+=ask_sum(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
else {
ssum+=ask_sum(1,dfn[top[y]],dfn[y]);
y=fa[top[y]];
}
}
ssum+=ask_sum(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
printf("%d\n",ssum);
}//同上
lg P3178 [HAOI2015]树上操作
题面描述
有一棵点数为 N 的树，以点 1 为根，且树有点权。然后有 M 个操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
做法
关于子树内的修改，需要用到之前的 e n en en数组了。
对于子树内的修改，只需在线段树上修改 d f n [ x ] dfn[x] dfn[x]到 e n [ x ] en[x] en[x]这一段区间。
然后就是注意会爆 i n t int int，本蒟蒻就是因为查不出具体哪里爆的 i n t int int，一怒之下全开了 l o n g long long l o n g long long.
#include<bits/stdc++.h>
#define len(p) (t[p].r-t[p].l+1)
#define ll long long
using namespace std;
const ll N=1e5+86;
struct edge{
ll y,nxt;
}Edge[N<<1];
ll Link[N],len,sze[N],son[N],fa[N],top[N],dep[N],dfn[N],rnk[N],tot,en[N],n,m,v[N];
void insert(ll x,ll y) {
Edge[++len]={y,Link[x]};
Link[x]=len;
}
void dfs1(ll now,ll fath) {
sze[now]=1;son[now]=-1;fa[now]=fath;dep[now]=dep[fath]+1;
for(ll i=Link[now];i;i=Edge[i].nxt) {
ll y=Edge[i].y;
if(dep[y]) continue;
dfs1(y,now);
sze[now]+=sze[y];
if(son[now]==-1||sze[son[now]]<sze[y]) son[now]=y;
}
}
void dfs2(ll now,ll ttp) {
top[now]=ttp;dfn[now]=++tot;rnk[tot]=now;
if(son[now]==-1) {
en[now]=tot;
return ;
}
dfs2(son[now],ttp);
for(ll i=Link[now];i;i=Edge[i].nxt) {
ll y=Edge[i].y;
if(y==son[now]||y==fa[now]) continue;
dfs2(y,y);
}
en[now]=tot;
}
struct tree{
ll l,r;
ll val,lazy;
}t[N<<2];
void pushup(ll p) {
t[p].val=t[p<<1].val+t[p<<1|1].val;
}
void build(ll p,ll l,ll r) {
t[p].l=l;t[p].r=r;
if(l==r) {
t[p].val=v[rnk[l]];
return ;
}
ll mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void pushdown(ll p) {
if(t[p].lazy) {
t[p<<1].val+=(t[p<<1].r-t[p<<1].l+1)*t[p].lazy;
t[p<<1|1].val+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].lazy;
t[p<<1].lazy+=t[p].lazy;t[p<<1|1].lazy+=t[p].lazy;
t[p].lazy=0;
}
}
void change(ll p,ll l,ll r,ll v) {
if(t[p].l>=l&&t[p].r<=r) {
t[p].val+=(t[p].r-t[p].l+1)*v;
t[p].lazy+=v;
return ;
}
pushdown(p);
ll mid=t[p].l+t[p].r>>1;
if(l<=mid) change(p<<1,l,r,v);
if(mid<r) change(p<<1|1,l,r,v);
pushup(p);
}
ll ask_sum(ll p,ll l,ll r) {
if(t[p].l>=l&&t[p].r<=r)
return t[p].val;
pushdown(p);
ll mid=t[p].l+t[p].r>>1;ll ssum=0;
if(l<=mid) ssum+=ask_sum(p<<1,l,r);
if(mid<r) ssum+=ask_sum(p<<1|1,l,r);
return ssum;
}
void Q_S(ll x) {
ll ans=0;
while(top[x]!=1) {
ans+=ask_sum(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
ans+=ask_sum(1,dfn[1],dfn[x]);
printf("%lld\n",ans);
}
int main() {
// freopen("haoi2015.in","r",stdin);
// freopen("haoi2015.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=n;i++) scanf("%lld",&v[i]);
for(ll i=1,x,y;i<n;i++) {
scanf("%lld%lld",&x,&y);
insert(x,y);
insert(y,x);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(m--) {
ll op,x,a;
scanf("%lld",&op);
if(op==1) {
scanf("%lld %lld",&x,&a);
change(1,dfn[x],dfn[x],a);
}
if(op==2) {
scanf("%lld %lld",&x,&a);
change(1,dfn[x],en[x],a);
}
if(op==3) {
scanf("%lld",&x);
Q_S(x);
}
}
return 0;
}
lg P2146 [NOI2015] 软件包管理器
题目背景
Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 homebrew 都是优秀的软件包管理器。
题面描述
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 a a a 依赖软件包 b b b，那么安装软件包 a a a 以前，必须先安装软件包 b b b。同时，如果想要卸载软件包 b b b，则必须卸载软件包 a a a。
现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 0 0 0 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 0 0 0 号软件包不依赖任何一个软件包。且依赖关系不存在环（即不会存在 m m m 个软件包 a 1 , a 2 , … , a m a_1,a_2, \dots , a_m a1,a2,…,am，对于 i < m i<m i<m， a i a_i ai 依赖 a i + 1 a_{i+1} ai+1，而 a m a_m am 依赖 a 1 a_1 a1 的情况）。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。
注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 0 0 0。
做法
题面很长，容易把人吓着。
但好好理理思路，就会发现他问的问题的实质：
install：询问该节点到根节点的路径上有多少不为1，并将其改为1.
uninstall：询问该节点的子树上有多少个1，并将其改为0.
看出实质之后其实也就是板子了。
#include<bits/stdc++.h>//不想写注释了，大家凑合看看得了，in是安装，out是卸载
#define len(p) (t[p].r-t[p].l+1)
using namespace std;
const int N=1e5+86;
struct edge{
int y,nxt;
}Edge[N<<2];
int Link[N<<1],len,top[N<<1],sze[N<<1],fa[N<<1],son[N<<1],dep[N<<1],dfn[N<<1],rnk[N<<1],tot,n,m,en[N<<1];
void insert(int x,int y) {
Edge[++len]={y,Link[x]};
Link[x]=len;
}
void dfs1(int now,int fath) {
son[now]=-1;fa[now]=fath;dep[now]=dep[fath]+1;sze[now]=1;
for(int i=Link[now];i;i=Edge[i].nxt) {
int y=Edge[i].y;
if(dep[y]) continue;
dfs1(y,now);
sze[now]+=sze[y];
if(son[now]==-1||sze[son[now]]<sze[y]) son[now]=y;
}
}
void dfs2(int now,int ttp) {
top[now]=ttp;dfn[now]=++tot;rnk[tot]=now;
if(son[now]==-1) {
en[now]=tot;
return ;
}
dfs2(son[now],ttp);
for(int i=Link[now];i;i=Edge[i].nxt) {
int y=Edge[i].y;
if(y==fa[now]||y==son[now]) continue;
dfs2(y,y);
}
en[now]=tot;
}
struct tree{
int l,r,val,lazy;
}t[N<<2];
void pushup(int p) {
t[p].val=t[p<<1].val+t[p<<1|1].val;
}
void build(int p,int l,int r) {
t[p].l=l;t[p].r=r;
if(l==r) return ;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void pushdown(int p) {
if(t[p].lazy==1) {
t[p<<1].val=len(p<<1);
t[p<<1|1].val=len(p<<1|1);
t[p<<1].lazy=1;t[p<<1|1].lazy=1;
t[p].lazy=0;
}
if(t[p].lazy==2) {
t[p<<1].val=t[p<<1|1].val=0;
t[p<<1].lazy=t[p<<1|1].lazy=2;
t[p].lazy=0;
}
}
int change_in(int p,int l,int r) {
if(t[p].l>=l&&t[p].r<=r) {
int ans = len(p)-t[p].val;
t[p].val=len(p);
t[p].lazy=1;
return ans;
}
pushdown(p);
int mid=t[p].l+t[p].r>>1,ans=0;
if(l<=mid) ans+=change_in(p<<1,l,r);
if(mid<r) ans+=change_in(p<<1|1,l,r);
pushup(p);
return ans;
}
int change_out(int p,int l,int r) {
if(t[p].l>=l&&t[p].r<=r) {
int ans = t[p].val;
t[p].val=0;
t[p].lazy=2;
return ans;
}
pushdown(p);
int mid=t[p].l+t[p].r>>1,ans=0;
if(l<=mid) ans+=change_out(p<<1,l,r);
if(mid<r) ans+=change_out(p<<1|1,l,r);
pushup(p);
return ans;
}
void Q_C(int x) {
int ans=0;
while(top[x]!=1) {
ans+=change_in(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
ans+=change_in(1,dfn[1],dfn[x]);
printf("%d\n",ans);
}
char ch[10];
int main() {
freopen("manager.in","r",stdin);
freopen("manager.out","w",stdout);
scanf("%d",&n);
for(int i=2,x;i<=n;i++) {
scanf("%d",&x);
insert(x+1,i);
insert(i,x+1);
}
dfs1(1,0);dfs2(1,1);
build(1,1,n);
scanf("%d",&m);
while(m--) {
int x;
scanf("%s%d",ch,&x);
if(ch[0]=='i') Q_C(x+1);
else printf("%d\n",change_out(1,dfn[x+1],en[x+1]));
}
return 0;
}//代码水长度
写在结尾
今天就写到这里，剩下的坑慢慢补。
明天模拟赛，%铭神，%米神，%莱依拉。
大神保佑