p3379、LQB14H 最近公共祖先LCA(倍增法)

最近公共祖先

最近公共祖先，就是两个节点的所有公共祖先中最近的那一个。

如图，2和7的最近公共祖先是5，2和4的最近公共祖先是1，2和1的最近公共祖先是1。

传统思路

如上图所示，怎么去求2和7的公共祖先呢？

• 第一步，先让2退到和7同层，即5的位置，
• 第二步，让5和4一起向后跳，直到两者相遇
• 第一次相遇的点，就是最近公共祖先。

倍增算法、ST表

但直接一步一步的跳效率显然不高，因为如果2的深度特别深，他就需要跳跃很多次才能来到和7同层的位置，因此就有了倍增算法。

例如从9到1，原来的方法是连续跳4次，现在是先跳到6，再跳到1，只需要跳两次。

通过上面的分析，我们需要两个很关键的信息

• dep[u] u节点的深度
• fa[u][i] u节点向上跳2^i到达的节点

倍增法求LCA的步骤

1. dfs一遍，创建st表
2. 先跳到同一层
3. 再跳到最近公共祖先的下一层

模板

void dfs(int u,int father)
{
    
	dep[u] = dep[father] + 1;
	
	fa[u][0] = father;//向上跳1步是father
	for(int i = 1;i<=20;i++)
	{
    
		fa[u][i] = fa[fa[u][i-1]][i-1];
	}
	
	for(int v : e[u])
	{
    
		if(v != father) dfs(v,u);
	}
}

int LCA(int u,int v)
{
    
	if(dep[u] < dep[v) swap(u,v);
		
	//先跳到同一层
	for(int i = 20;i>=0;i--)
	{
    
		if(dep[fa[u][i]] >= dep[v])
		{
    
			u = fa[u][i];
		}	
	}
	if(u == v) return v;
	//再跳到LCA的下一层
	for(int i = 20;i>=0;i--)
	{
    
		if(fa[u][i] != fa[v][i])
		{
    
			u = fa[u][i], v=fa[v][i];
		}
	}
	return fa[u][0];
}

LQB14H

题目

题目信息：
某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N − 1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个景点：A1, A2, . . . , AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 个景点。具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览 A1, A2, . . . , Ai−1, Ai+1, . . . , AK, (1 ≤ i ≤ K)。
请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

输入输出：
第一行包含 2 个整数 N 和 K。
以下 N − 1 行，每行包含 3 个整数 u, v 和 t，代表景点 u 和 v 之间有摆渡车线路，花费 t 个单位时间。
最后一行包含 K 个整数 A1, A2, . . . , AK 代表原定游览线路。

输出 K 个整数，其中第 i 个代表跳过 Ai 之后，花费在摆渡车上的时间。

输入：
6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1

输出：
10 7 13 14

解法步骤

1. 先进行dfs，把st表和点到根节点的距离数组dis求出
2. A1-A2的距离=dis[A1] + dis[A2] - 2*dis[LCA(A1,A2)];
3. 去掉A[i]节点的距离=原来的距离 - A[i-1]到A[i] - A[i]到A[i+1] + A[i-1]到A[i+1]的距离

代码样例

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MAX_N=5e5+1;
int N,K,dep[MAX_N],fa[MAX_N][21],A[MAX_N];

vector<int> E[MAX_N],W[MAX_N];
LL dis[MAX_N];


void dfs(int u,int father)
{
    
	dep[u] = dep[father] + 1;
	
	fa[u][0] = father;
	for(int i = 1;i<=20;i++)
	{
    
		fa[u][i] = fa[fa[u][i-1]][i-1];
	}
	
	for(int i = 0;i<E[u].size();i++)
	{
    
		int v = E[u][i], w = W[u][i];
		if(v == father) continue;
		dis[v] = dis[u] + w;
		
		dfs(v,u);		
	}
}





int LCA(int u,int v)
{
    
	if(dep[u] < dep[v]) swap(u,v);
	
	//第一阶段：跳到同一层 
	for(int i = 20;i>=0;i--)
	{
    
		if(dep[fa[u][i]] >= dep[v])
		{
    
			u = fa[u][i];
		}
	}
	
	if(u == v) return u;
	
	//第二阶段：一起跳到LCA的下一层
	for(int i = 20;i>=0;i--)
	{
    
		if(fa[u][i] != fa[v][i])
		{
    
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	
	return fa[u][0];
}



LL path_dis(int u,int v)
{
    
	if(!u || !v) return 0;
	return dis[u]+dis[v]-2*dis[LCA(u,v)];
}



int main()
{
    
	cin >> N >> K;
	for(int i = 1;i<N;i++)
	{
    
		int u,v,t;
		cin >> u >> v >> t;
		
		E[u].push_back(v);
		E[v].push_back(u);
		W[u].push_back(t);
		W[v].push_back(t);
	}
	
	dfs(1,0);
	
	LL ans = 0;//原来路线要花费的时间
	for(int i = 1;i<=K;i++)
	{
    
		cin >> A[i];
		ans += path_dis(A[i],A[i-1]);
	}

	for(int i = 1;i<=K;i++)
	{
    
		cout << ans - path_dis(A[i-1],A[i]) - path_dis(A[i],A[i+1]) + path_dis(A[i-1],A[i+1]) << endl;
	}
	return 0;
} 

总结