P8805 [蓝桥杯 2022 国 B] 机房

分析

是一道lca题目，可以直接套模板 + 前缀和处理点权

具体思路：

1.n台电脑用n-1条网线相连，任意两个节点之间有且仅有一条路径（拆分成各自到公共祖先节点的路径——lca）；

2.“延迟时间”：看成是节点点权（要求一条链上某个区间的值——前缀和）

——用sum[]存储根节点到 i 节点的点权和

LCA

三种求法：

（1）朴素求法：

先将两点位于同一深度，然后同时向上跳；一次查询：O(n^2)

（2）倍增求法：

朴素求法的改进版（朴素是一步一步跳，倍增是用f[][]优化，每次向上都是以其父节点为目标）

（3）Tarjan（留一下，还没学~）

倍增求法的步骤：

1.存图/树

2.dfs(int x,int father)更新f[][]（表示节点 i 的第2^j个祖先节点）、d[]（深度）

（1）更新d[x]和f[x][0]

（2）for(1~20)更新f[x][i]

（3）for(遍历邻接点)递归dfs()

3.lca

（1）先将两点跳到同一深度（深度大的往上跳）

（2）若相等，则该点就是lca；若不相等，则从大到小，如果f[][]不等，则更新两点，lca=f[x][0]

代码 

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010;
int head[N],d[N],f[N][30],a[N],sum[N],cnt,n,m;
struct edges{
	int to;
	int ne;
}e[N*2];//存两条边记得数组开成2倍

//初始化别忘了（容易忘建议直接写main中）
void init()
{
	memset(head,-1,sizeof head);
}
//链式前向星存边
void addedge(int u,int v)
{
	e[cnt].to = v;
	e[cnt].ne = head[u];
	head[u] = cnt ++;
}
//dfs处理d[]、f[][]、sum[]
void dfs(int x,int father)
{
	d[x] = d[father] + 1;
	f[x][0] = father;
	sum[x] = sum[f[x][0]] + a[x];  //lca模板多了这一步~
	for(int i = 1;i <= 20;i ++)
	{
		f[x][i] = f[f[x][i-1]][i-1];
	}
	for(int i = head[x];i != -1;i = e[i].ne)
	{
		int j = e[i].to;
		if(j == father) continue; //加的是双向边，所以邻接点有其父节点，遍历时跳过
		dfs(j,x);	//递归遍历
	}
	return ;
}
//lca找到最近公共祖先节点
int lca(int u,int v)
{
	if(d[u] < d[v]) swap(u,v);
		for(int i = 20;i >= 0;i --)
		{
			if(d[f[u][i]] >= d[v]) u = f[u][i];
		}
		if(u == v)
		{
			return u;
		}
		for(int i = 20;i >= 0;i --)
		{
			if(f[u][i] != f[v][i])
			{
				u = f[u][i];
				v = f[v][i];
			}
		}
		return f[u][0];
}

int main()
{
	init();
	scanf("%d %d",&n,&m);
	for(int i = 0;i < n - 1;i ++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		a[u] ++,a[v] ++;
		addedge(u,v),addedge(v,u);
	}
	dfs(1,0);
	while(m --)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		int mid = lca(u,v);
		int ans = sum[u] + sum[v] - 2 * sum[mid] + a[mid];  //两点之间的权值和
		printf("%d\n",ans);
	}
	return 0;
}