与图论的邂逅08:树上倍增

淩亂°似流年 2021-12-24 16:23 203阅读 0赞

## 什么是树上倍增？ ##

### 顾名思义，就是在树上成倍地增长，可以用于解决一些静态树的查询问题。 ###

--------------------

#### 放出例题：给定一棵根节点为1的n个节点的树，并给出树上两个点u,v，求它们的最近公共祖先。 ####

#### 我们可以预处理出每个点的父亲节点*fa*和深度*dep*，然后选择u,v中深度较大者不断地往父亲节点走，当u,v深度相同时判断：u,v是否为同一个点。如果是，那么答案就是u或者v；否则，u,v同时向着各自的父亲节点走，当两个点的父亲节点相同时，fa\[u\]或者fa\[v\]就是答案。时间复杂度为O(N)。 ####

//口胡一段代码(未检查) int fa[maxn],dep[maxn]; //预处理部分，时间复杂度为O(N) void dfs_getfa(int u,int pre){ for(register int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(v==fa[u]) continue; dep[v]=dep[u]+1,fa[v]=u; dfs_getfa(v,u); } } //求lca部分，时间复杂度为O(N) inline int lca(int u,int v){ if(dep[u]>dep[v]) swap(u,v); while(dep[fa[v]]>=dep[u]) v=fa[v]; if(u==v) return u; while(fa[u]!=fa[v]) u=fa[u],v=fa[v]; return fa[u]; }

--------------------

#### 现在问题改一下，仍然给你一棵根节点为1的n个点的树，下面有m个询问，每个询问都给出两个点u,v，求每个询问的lca(u,v)。1≤n,m≤500000。 ####

#### 如果还是之前的做法，那么时间复杂度就是O(NM)，肯定会爆掉对吧,,,,,,所以这里我们将会用到一种算法——树上倍增。之前只是一步一步地跳实在太慢，我们一次跳个2的k次方步如何？根据二进制转化的思想，一个数x总能背拆成如下的样子： ####

\\\[ x=2^\{k\_1\}+2^\{k\_2\}+2^\{k\_3\}+...... \\\]

#### 所以每次跳2的若干次方，我们总能跳到想要的位置。还是用上面的思路，先预处理出深度dep和数组fa(i,j)，表示节点i往上跳2的j次方步到达的节点，那么f(i,j)=f(f(i,j-1),j-1)，初始化f(i,j)为i的父亲节点。然后选择深度大的节点先跳，再两个点一起跳。时间复杂度为O((N+M)logN)。 ####

int fa[maxn][20],dep[maxn],maxdep; //预处理部分，时间复杂度为O(NlogN) void dfs_getfa(int u,int pre){ for(register int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(v==pre) continue; dep[v]=dep[u]+1,fa[v][0]=u; for(register int j=1;j<=maxdep;j++) fa[v][j]=fa[fa[v][j-1]][j-1]; dfs_getfa(v,u); } } //求lca部分，单次时间复杂度为O(logN) inline int lca(int u,int v){ if(dep[u]>dep[v]) swap(u,v); for(register int i=maxdep;i>=0;i--) if(dep[fa[v][i]]>=dep[u]) v=fa[v][i]; if(u==v) return u; for(register int i=maxdep;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } //main函数中 maxdep=(int)log(n)/log(2)+1;

--------------------

### 上面是树上倍增最简单的实例。下面再给出一道例题： ###

#### 给出一棵n个节点的树，下面有m次询问，每次询问给出树上两个点u,v，求u到v的路径上边权的最大值。 ####

#### 明确思路。虽然路径上有很多个点，但我们可以用唯一的三个点来确定这条路径——u,v和lca(u,v)。所以问题可以转化为：求出u到lca(u,v)的路径上边权的最大值为max1，并求出v到lca(u,v)的路径上边权的最大值max2，答案为max(max1,max2)。而我们上面单可以跳到lca罢了。可以类比着求fa(i,j)的做法，设max\_edge(i,j)表示节点i到f(i,j)的路径上边权最大值，那么显然：max\_edge(i,j)=max(max\_edge(i,j-1),max\_edge(fa(i,j-1),j-1))，初始化max\_edge(i,0)为i和i的父亲节点之间的边的边权。然后我们倍增地往lca跳，统计跳过的地方的边权最大值即可，时间复杂度也是O((N+M)logN)。 ####

int fa[maxn][20],max_edge[maxn][20],dep[maxn],maxdep; void dfs_getfa(int u,int pre){ for(register int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(v==pre) continue; dep[v]=dep[u]+1,fa[v][0]=u,max_edge[v][0]=e[i].dis; for(register int j=1;j<=maxdep;j++) fa[v][j]=fa[fa[v][j-1]][j-1],max_edge[v][j]=max(max_edge[v][j-1],max_edge[fa[v][j-1]][j-1]); dfs_getfa(v,u); } } inline int lca(int u,int v){ if(dep[u]>dep[v]) swap(u,v); int ans=-INF; for(register int i=maxdep;i>=0;i--) if(dep[fa[v][i]]>=dep[u]) ans=max(ans,max_edge[v][i]),v=fa[v][i]; if(u==v) return ans; for(register int i=maxdep;i>=0;i--) if(fa[u][i]!=fa[v][i]) ans=max(ans,max(max_edge[u][i],max_edge[v][i])),u=fa[u][i],v=fa[v][i]; return max(ans,max(max_edge[u][0],max_edge[v][0])); } //main函数中 maxdep=(int)log(n)/log(2)+1;

#### 求最小值或者边权和也是类似的做法。 ####

封

--------------------

坟

#### 再来一道例题：给出一棵n个节点的树，下面有m次操作，"1,i,w"表示修改编号为i的边的边权为w，"2,u,v"表示求节点u,v之间的路径上边权最大值。 ####

#### 这道题倍增就做不了了，因为无法快速修改max\_edge数组。这得让树剖来做，时间复杂度可以做到O(MlogNlogN)。所以，树上倍增只适合做静态树(不带修改的)上的问题。当然树剖也可以做静态树的问题，但树上倍增表现更好(除了求lca). ####

转载于:https://www.cnblogs.com/akura/p/10890805.html