专栏文章

P4281 紧急集合 lca 树上点间距离计算

WWild_Of_The_World
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqa6mvw
此快照首次捕获于
2025/12/04 01:28
3 个月前
此快照最后确认于
2025/12/04 01:28
3 个月前
查看原文
这道题，很容易想到先把最近的人聚在一起，剩下一个人去找他们，加上是树，想到求Lca。集合的点肯定是两两的Lca之一。最简单思路就是3个点都算出来。
1.不把6个点都算出来，又为了避免都在同一子树上往上走的浪费，故想到了以其中一个点为根，跑tarjan
40pts：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,s,ans;
int head[N],nxt[N],to[N],cnt;
int deep[N],fa[N],vis[N],aim[N],Lca,ok;
void add(int u,int v){
	nxt[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	return ;
}
int find(int x){
	if(fa[x]!=x) return fa[x]=find(fa[x]);
	return x;
}
void dfs(int x,int father){
	fa[x]=x;
	vis[x]=1;
	deep[x]=deep[father]+1;
	int v;
	for(int i=head[x];i;i=nxt[i]){
		v=to[i];
		if(ok==1) return ;
		if(!vis[v]){
			dfs(v,x);
			fa[v]=x;
		}
	}
	if(vis[aim[x]])	Lca=find(aim[x]),ok=1;
	return ;
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b,c;
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}	
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a,&b,&c);
		memset(vis,0,sizeof(vis));
//		for(int j=1;j<=n;++j) fa[j]=j;
		ok=0;
		aim[b]=c,aim[c]=b;
		dfs(a,0);
		aim[b]=aim[c]=0;
		printf("%d %d\n",Lca,deep[b]+deep[c]-deep[Lca]-1);
	}
	return 0;
}
因为每个问都要跑一遍，O（nm）T掉，卡常卡到70tps
70pts：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,s,ans;
int head[N],nxt[N],to[N],cnt;
int deep[N],fa[N],vis[N],aim[N],Lca,ok;
void add(int u,int v){
	nxt[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	return ;
}
int find(int x){
	if(fa[x]!=x) return fa[x]=find(fa[x]);
	return x;
}
int st[N],top;
void dfs(int x,int father){
	fa[x]=x;
	vis[x]=1;
	st[++top]=x;
	deep[x]=deep[father]+1;
	int v;
	for(int i=head[x];i;i=nxt[i]){
		v=to[i];
		if(ok==1){
			return ;
		}
		if(!vis[v]){
			dfs(v,x);
			fa[v]=x;
		}
	}
	if(vis[aim[x]])	
	{
		Lca=find(aim[x]),ok=1;
		while(top){
			vis[st[top]]=0;
			top--;
		}
	}
	return ;
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b,c;
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}	
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a,&b,&c);
//		memset(vis,0,sizeof(vis));
//		for(int j=1;j<=n;++j) fa[j]=j;
		ok=0;
		aim[b]=c,aim[c]=b;
		dfs(a,0);
		aim[b]=aim[c]=0;
		printf("%d %d\n",Lca,deep[b]+deep[c]-deep[Lca]-1);
	}
	return 0;
}
优化不下去了，回到一开始的想法，算3个Lca，取最深的一个
100pts：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m;
int head[N],nxt[N],to[N],cnt;
int deep[N],fa[N][26];		//24会因为数组越界出错 
void add(int u,int v){
	nxt[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	return ;
}
void dfs(int x,int father){
	deep[x]=deep[father]+1;
	fa[x][0]=father;
	for(int i=1;(1<<i)<=deep[x];++i)	fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=head[x];i;i=nxt[i])	if(to[i]!=father) dfs(to[i],x);	
	return ;
}
int lca(int a,int b){
	if(deep[a]<deep[b]) swap(a,b);
	for(int i=24;i>=0;i--)	if(deep[a]-(1<<i)>=deep[b]) a=fa[a][i];
	if(a==b)	return a;
	for(int i=24;i>=0;i--)	
		if(fa[a][i]!=fa[b][i]){			
			a=fa[a][i],b=fa[b][i];
		}
	return fa[a][0];
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b,c,Lca,Lcb,Lcc;
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}	
	dfs(1,0);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		Lca=lca(a,b),Lcb=lca(b,c),Lcc=lca(c,a);
		if(deep[Lcb]>deep[Lca]) swap(a,b),swap(Lca,Lcb);
		if(deep[Lcc]>deep[Lca]) swap(a,c),swap(Lca,Lcc);
		printf("%d %d\n",Lca,deep[a]+deep[b]+deep[c]-deep[Lca]-deep[Lcb]-deep[Lcc]);
	}
	return 0;
}
在计算距离时一开始想到是这样的：
CPP
deep[a]+deep[b]-deep[Lca]-deep[c]
让c最高
但这样只在3个点都在同一颗子树上才成立
by the way，计算Lca时要注意倍增数组不要越界，自己写的时候出现好几次这个问题，唐完了

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...