例题
POJ 3237()
BZOJ 3083
BZOJ 3531
BZOJ 3589
BZOJ 3626
将树上问题通过dfs序的性质转换为区间问题,从而对树上修改时就可转化为相应的区间修改。再通过引入重儿子,重链一系列概念将时间复杂度也变成了可以接受的层次
通过两次dfs求出树上一系列的信息
void dfs1(int u){
sz[u]=1;
dep[u]=dep[fa[u]]+1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v==fa[u]) continue;
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u]=v;
}
}
void dfs2(int u){
static int T=0;
seq[pos[u]=++T]=u;
if(son[fa[u]]==u) top[u] = top[fa[u]];
else top[u]=u;
if(son[u]) dfs2(son[u]);
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v!=fa[u]&&v!=son[u]) dfs2(v);
}
}
更新树上信息可分为 更新点权和更新边权
由于dfs序rk[]和pos[]数组是点的相应顺序排列的
所以当处理点权的时候我们直接更新两点间的信息即可
而当更新边权时,我们选择架空根节点,那么点权就可以变成边权了,所以对应跳重链的过程也有一点不同。具体看代码
点权
int QueryMax(int x,int y){
int re=-inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
re=max(re,treeQueryMax(1,1,n,pos[top[x]],pos[x]));
x=fa[top[x]];
}
if(dep[x]<dep[y])
swap(x,y);
return re=max(re,treeQueryMax(1,1,n,pos[y],pos[x]));
}
边权
架空根节点后 dfs序的每个点的价值就变为该点与其父亲节点的边权值
那么在跳重链的过程中,假如dep[x]<dep[y],我们更新的其实应该是son[x]-y对应的边权(即点权)因为每个点x对应的权值是只向他的父亲的。
所以当两个点相同时就已经更新完成了
int QueryMax(int x,int y){
int re=-inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
re=max(re,treeQueryMax(1,1,n,pos[top[x]],pos[x]));
x=fa[top[x]];
}
if(x==y) return ;
if(dep[x]<dep[y]) swap(x,y);
return re=max(re,treeQueryMax(1,1,n,pos[son[y]],pos[x]));
}