Yurchiu's Blog
Yurchiu
An AFO whker.
  首页
  归档
158
  标签
81
  分类
24
  说说
  关于
  留言
  链接
  设置

一些关于 LCA 的题目

Yurchiu 2021-02-24, 18:05:31 3.6k 隐藏左右两栏 展示左右两栏
首页 / 一些关于 LCA 的题目

这里是一些关于 LCA 的题目。

P3398 仓鼠找 sugar

题意

在一棵有 nn （≤105\le10^5）个节点的树上，有 qq （≤105\le10^5）个询问，每次询问两个点对 (a,b)(a,b)，(c,d)(c,d) 之间的最短路径的点集是否有交。

点击查看题解

题解

若树上两条路径相交，则其中一条路径的 LCA 一定在另一条路径上。

一个感性的解释：设树根在你所画的图的最上面，若不满足上述条件，则两条路径一定是交叉的，成 X 或 Y 形，这显然跟树的定义不符（一个点仅有一个前驱）。

然后就是判断其中一条路径的 LCA 是否在另一条路径上了。一个判断的依据：一个点若在一条路径上，则这个点到路径左端点的距离 ++ 这个点到路径右端点的距离 == 这个路径的长度。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=500000+10,Log=20;
	struct edge{int nxt,to;}e[N*2];
	int n,Root,Q,cnt=0,d[N],head[N],f[Log+5][N];
	void add(int a,int b){e[++cnt]=(edge){head[a],b};head[a]=cnt;}
	void dfs(int root)
	{
		for(int i=head[root];i;i=e[i].nxt)
		{
			int son=e[i].to;
			if(f[0][root]==son) continue;
			d[son]=d[root]+1;f[0][son]=root;dfs(son);
		}
	}
	void init()
	{
		d[Root]=1;dfs(Root);f[0][Root]=Root;
		for(int i=1;i<=Log;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=f[i-1][f[i-1][j]];
	}
	int LCA(int x,int y)
	{
		if(d[x]<d[y]) swap(x,y);
		for(int i=Log;i>=0;i--) if(d[f[i][x]]>=d[y]) x=f[i][x];
		if(x==y) return x;
		for(int i=Log;i>=0;i--)
			if(f[i][x]!=f[i][y]) 
				x=f[i][x],y=f[i][y];
		return f[0][x];
	}
	int dis(int x,int y)
	{
		int ret=0,lca=LCA(x,y);
		ret+=abs(d[x]-d[lca]);
		ret+=abs(d[y]-d[lca]);
		return ret;
	}
	void yzmain()
	{
		int t1,t2,t3,t4,l12,l34;
		scanf("%d%d",&n,&Q);Root=1;
		for(int i=1;i<=n-1;i++)
			scanf("%d%d",&t1,&t2),add(t1,t2),add(t2,t1);
		init();
		for(int i=1;i<=Q;i++)
		{
			scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
			l12=LCA(t1,t2),l34=LCA(t3,t4);
			if(dis(t3,t4)==dis(t3,l12)+dis(l12,t4) ||
			   dis(t1,t2)==dis(t1,l34)+dis(l34,t2) )
		         printf("Y\n");		
			else printf("N\n"); 	
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P1967 [NOIP2013 提高组] 货车运输

题意

是文章最小生成树 2 中的题目 P1396 营救的“加强版”。1 万个点，5 万个边，有 3 万次询问，每次给定两点，求它们之间的一条路径，令路径上的最小边权最大。输出此路径最小边权。即，求两点最大瓶颈路的瓶颈。

点击查看题解

题解

由于本题，这篇文章的标签才多了个“最小生成树”。

类似“营救”一题地，先构建最大生成树，按这棵树建新图。但这样要是在这个图上随便搜索一下就超时了。考虑加速求一条路径的最小边权。注：可以将边权转化为点权。

我们使用倍增来加速。先钦定每个连通块（图不一定连通）的一个节点为根。此时每条路径就相当于左端点到 LCA 的路径加右端点到 LCA 的路径。设 A(i,j)A(i,j) 表示 jj 点向上跳 2i2^i 个点所经过点权的最小值。状态转移方程和求 LCA 用的倍增数组类似，可见代码。当我们求两点的 LCA 时，我们也可以顺带求得最小值。

如何判断无解：只要看看两点是否在一个连通块中即可。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int M=50000+10,N=10000+10,Inf=2147483647/2,V=17;
	struct Road{int u,v,len;}road[M];
	struct Graph
	{
		struct edge{int nxt,to,len;}e[M*2];
		int head[N],cnt;
		Graph(){memset(head,0,sizeof(head));cnt=0;}
		void add(int a,int b,int c){e[++cnt]=(edge){head[a],b,c};head[a]=cnt;}
	}Tree;
	struct UFDS
	{
		int dad[M],n;
		void init(int p){ n=p; for(int i=1;i<=n;i++) dad[i]=i; }
		int find(int x)
		{  
    		int root=x;  
    		while(root!=dad[root])
        		root=dad[root];
    		return root;  
		}
		void union_(int x,int y)
		{
    		int d1=find(x),d2=find(y);
    		dad[d1]=d2;
    		return;
		}
		bool check(int x,int y)
		{
    		int d1=find(x),d2=find(y);
    		if(d1==d2)
        		return 1;
    		return 0;
		}
	}ufds;
	int n,m,Q,s,t,f[V+5][N],d[N],A[V+5][N];
	bool cmp(Road a,Road b){ return a.len>b.len; }
	void kruskal()
	{
    	int num=0,ru,rv; 
    	sort(road+1,road+m+1,cmp);
    	for(int i=1;i<=m;i++)
    	{
       		ru=ufds.find(road[i].u),rv=ufds.find(road[i].v);
        	if(ru==rv)
            	continue;
			Tree.add(road[i].u,road[i].v,road[i].len);
			Tree.add(road[i].v,road[i].u,road[i].len);
			ufds.union_(ru,rv);
        	if(++num==n-1)
            	break;
    	}
	}
	void dfs(int now)
	{
		for(int i=Tree.head[now];i;i=Tree.e[i].nxt)
		{
			int to=Tree.e[i].to,len=Tree.e[i].len;
			if(f[0][now]!=to)
				d[to]=d[now]+1,f[0][to]=now,A[0][to]=len,dfs(to);
		}
		return;
	}
	int LCA(int u,int v)
	{
		int ret=Inf;
		if(d[u]>d[v]) swap(u,v);
		int tmp=d[v]-d[u];
		for(int i=V;i>=0;i--)
			if(tmp>=(1<<i))
				ret=min(ret,A[i][v]),v=f[i][v],tmp-=(1<<i);
		if(u==v) return ret;
		for(int i=V;i>=0;i--)
			if(f[i][u]!=f[i][v])
				ret=min(ret,min(A[i][u],A[i][v])),
				u=f[i][u],v=f[i][v];
		return min(ret,min(A[0][u],A[0][v]));
	}
	void yzmain()
	{
		int ta,tb,tc;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&ta,&tb,&tc),
			road[i]=(Road){ta,tb,tc};
		ufds.init(n);kruskal();
		for(int i=1;i<=n;i++)
			if(ufds.dad[i]==i) f[0][i]=i,A[0][i]=0,dfs(i);
		for(int i=1;i<=V;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=f[i-1][f[i-1][j]],
				A[i][j]=min(A[i-1][j],A[i-1][f[i-1][j]]);
		scanf("%d",&Q);
		for(int i=1;i<=Q;i++)
		{
			scanf("%d%d",&s,&t);
			if(ufds.find(s)!=ufds.find(t)) { printf("-1\n");continue; }
			printf("%d\n",LCA(s,t));
		}
		return;
	}	
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P4281 [AHOI2008]紧急集合 / 聚会

题意

给定一棵 nn 个节点的树以及 mm 次询问，每次询问给出 xx，yy，zz 三个节点，需要在树上找一个点 pp 使得 dis(x,p)+dis(y,p)+dis(z,p)dis(x,p)+dis(y,p)+dis(z,p) 取最小值（其中 dis(a,b)dis(a,b) 指 aa，bb 两点的距离），每一次询问输出满足条件的 pp 和此时的最小值。

点击查看题解

题解

我们先钦定这棵树树根为 11。然后 pp 点无非就三种情况：

  • 三点中两两 LCA 都相同：pp 点就是这个 LCA 啦！
  • 三点中有两对点 LCA 相同：pp 点就是这个 LCA 啦！如果是另一对点的 LCA，就徒增了一段到 pp 的距离。
  • 三点中两两 LCA 互不相同：其实这种情况不存在。根据“仓鼠找sugar”一题的“感性的解释”，三个点就相当于有四个点，其中有一对点重合。而这样一定会有一对点的 LCA 在另一对点所形成的路径上。不妨设 xx 和 yy 的 LCA 是 aa，aa 和 zz 的 LCA 为 bb，那么 xx 和 zz 的 LCA 以及 yy 和 zz 的 LCA 就相同了。

这样，我们可以将情况 1 合并到情况 2 中，通过求每两个点的 LCA，计算出三个点距离 LCA 的距离和，这样计算并比较 3 次，可得出答案。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=500000+10,Log=20;
	struct edge{int nxt,to;}e[N*2];
	int n,Root,Q,cnt=0,d[N],head[N],f[Log+5][N];
	void add(int a,int b){e[++cnt]=(edge){head[a],b};head[a]=cnt;}
	void dfs(int root)
	{
		for(int i=head[root];i;i=e[i].nxt)
		{
			int son=e[i].to;
			if(f[0][root]==son) continue;
			d[son]=d[root]+1;f[0][son]=root;dfs(son);
		}
	}
	void init()
	{
		d[Root]=1;dfs(Root);f[0][Root]=Root;
		for(int i=1;i<=Log;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=f[i-1][f[i-1][j]];
	}
	int LCA(int x,int y)
	{
		if(d[x]<d[y]) swap(x,y);
		for(int i=Log;i>=0;i--) if(d[f[i][x]]>=d[y]) x=f[i][x];
		if(x==y) return x;
		for(int i=Log;i>=0;i--)
			if(f[i][x]!=f[i][y]) 
				x=f[i][x],y=f[i][y];
		return f[0][x];
	}
	int dis(int x,int y)
	{
		int ret=0,lca=LCA(x,y);
		ret+=abs(d[x]-d[lca]);
		ret+=abs(d[y]-d[lca]);
		return ret;
	}
	void yzmain()
	{
		int tmp,t1,t2,t3,l12,l13,l23,pans,vans;
		scanf("%d%d",&n,&Q);Root=1;
		for(int i=1;i<=n-1;i++)
			scanf("%d%d",&t1,&t2),add(t1,t2),add(t2,t1);
		init();
		for(int i=1;i<=Q;i++)
		{
			scanf("%d%d%d",&t1,&t2,&t3);
			l12=LCA(t1,t2),l13=LCA(t1,t3),l23=LCA(t2,t3);
			pans=l12,vans=dis(t1,l12)+dis(t2,l12)+dis(t3,l12);
			tmp=dis(t1,l13)+dis(t2,l13)+dis(t3,l13);
			if(tmp<vans) pans=l13,vans=tmp;
			tmp=dis(t1,l23)+dis(t2,l23)+dis(t3,l23);
			if(tmp<vans) pans=l23,vans=tmp;
			printf("%d %d\n",pans,vans); 	
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P4180 [BJWC2010]严格次小生成树

题意

给定含 nn 个点，mm 条边的无向图，求其严格次小生成树。严格次小生成树定义为：如果最小生成树选择的边集是 EME_M，严格次小生成树选择的边集是 ESE_S，那么需要满足：∑e∈EMvalue(e)<∑e∈ESvalue(e)\sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)。其中，value(e)value(e) 表示边 ee 的权值。

点击查看题解

题解

要求严格次小生成树，我们需先求最小生成树。求出来后，由于最小生成树上 uu 到 vv 的路径一定是 uu 到 vv 的最小瓶颈路之一（“最小瓶颈路”的概念已在这篇文章中介绍），所以未纳入的边 (u,v)(u,v) 的边权一定大于等于 uu 到 vv 最小瓶颈路的瓶颈。

因此，我们枚举每一个未纳入最小生成树的边 (u,v)(u,v)，断掉原先 uu 到 vv 路径上的瓶颈（若瓶颈和这条边权值相等，断其次大瓶颈，从而保证严格次小），再把此边加入这棵树（其实不用真的加边），这样就生成了一棵劣于最小生成树的生成树。更新答案即可。

由于可能要断次大瓶颈，所以不仅要像“货车运输”一题那样要建立倍增数组存最大值，还要再开一个存次大值。各种细节见代码。

代码

注意这个代码有恶臭味。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define ll long long
	const ll M=3000000+10,N=1000000+10,V=20,Inf=1145141919810999999;//Inf 要开得足够大！
	struct Road{ll u,v,len;}road[M];
	struct Graph
	{
		struct edge{ll nxt,to,len;}e[M*2];
		ll head[N],cnt;
		Graph(){memset(head,0,sizeof(head));cnt=0;}
		void add(ll a,ll b,ll c){e[++cnt]=(edge){head[a],b,c};head[a]=cnt;}
	}Tree;
	struct UFDS
	{
		ll dad[M],n;
		void init(ll p){ n=p; for(ll i=1;i<=n;i++) dad[i]=i; }
		ll find(ll x)
		{   
    		while(x!=dad[x])
        		x=dad[x]=dad[dad[x]];
    		return x;
		}
		void union_(ll x,ll y)
		{
    		ll d1=find(x),d2=find(y);
    		dad[d1]=d2;
    		return;
		}
		bool check(ll x,ll y)
		{
    		ll d1=find(x),d2=find(y);
    		if(d1==d2)
        		return 1;
    		return 0;
		}
	}ufds;
	ll n,m,f[V+5][N],d[N],A[V+5][N],B[V+5][N];
	long long size=0,ans=Inf;
	bool cmp(Road a,Road b){ return a.len<b.len; }
	void kruskal()
	{
    	ll num=0,ru,rv; 
		ufds.init(n);
    	sort(road+1,road+m+1,cmp);
    	for(ll i=1;i<=m;i++)
    	{
       		ru=ufds.find(road[i].u),rv=ufds.find(road[i].v);
        	if(ru==rv)
            	continue;
			Tree.add(road[i].u,road[i].v,road[i].len);
			Tree.add(road[i].v,road[i].u,road[i].len);
			size+=road[i].len;//求最小生成树
			road[i].len=Inf;//去除已纳入最小生成树的边
			ufds.union_(ru,rv);
        	if(++num==n-1)
            	break;
    	}
	}
	void dfs(ll now)
	{
		for(ll i=Tree.head[now];i;i=Tree.e[i].nxt)
		{
			ll to=Tree.e[i].to,len=Tree.e[i].len;
			if(f[0][now]!=to)
				d[to]=d[now]+1,f[0][to]=now,A[0][to]=len,dfs(to);
		}
		return;
	}
	void LCAinit()
	{
		f[0][1]=1,dfs(1);
		for(ll i=1;i<=V;i++)
			for(ll j=1;j<=n;j++)
			{
				f[i][j]=f[i-1][f[i-1][j]];
				A[i][j]=max(A[i-1][j],A[i-1][f[i-1][j]]);//最大值
				B[i][j]=max(B[i-1][j],B[i-1][f[i-1][j]]);//严格次大值
				if(A[i-1][j]!=A[i-1][f[i-1][j]])//注意！！！
					//如果两者相等还更新次大值，次大值就不严格了
					B[i][j]=max(B[i][j],min(A[i-1][j],A[i-1][f[i-1][j]]));
			}
	}
	ll LCA(ll x,ll y,ll C)
	{
		ll ret=-Inf;
		if(d[x]<d[y]) swap(x,y);
		for(ll i=V;i>=0;i--) 
			if(d[f[i][x]]>=d[y]) 
			{
				if(A[i][x]<C) ret=max(ret,A[i][x]);//如果断边边权大于等于加入的边
				else ret=max(ret,B[i][x]);//就不是严格次小了，所以用次大边更新
				x=f[i][x];
			}	
		if(x==y) return ret;
		for(ll i=V;i>=0;i--)
			if(f[i][x]!=f[i][y]) 
			{
				if(A[i][x]<C) ret=max(ret,A[i][x]);
				else ret=max(ret,B[i][x]);
				if(A[i][y]<C) ret=max(ret,A[i][y]);
				else ret=max(ret,B[i][y]);
				x=f[i][x],y=f[i][y];
			}
		if(A[0][x]<C) ret=max(ret,A[0][x]);
		else ret=max(ret,B[0][x]);
		if(A[0][y]<C) ret=max(ret,A[0][y]);
		else ret=max(ret,B[0][y]);
		return ret;
	}
	void yzmain()
	{
		ll ta,tb,tc;
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=m;i++)
			scanf("%lld%lld%lld",&ta,&tb,&tc),
			road[i]=(Road){ta,tb,tc};
		kruskal();LCAinit();//先构建最小生成树
		sort(road+1,road+1+m,cmp);
		for(ll i=1;i<=m;i++)
		{
			ll len=road[i].len; if(len==Inf) break;//枚举完边就退出
			ll u=road[i].u,v=road[i].v;
			ans=min(ans,size-LCA(u,v,len)+len);//次小生成树=最小生成树-瓶颈+新边
		}
		printf("%lld\n",ans);
		return;
	}	
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}



本文作者：Yurchiu

本文链接：https://yz-hs.github.io/47cfbdb04aea/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。


OI 倍增 树 最小生成树 LCA 一些
最后更新：2023-08-21, 23:18:21
By Yurchiu.
最近更新旧文更新
[Works] 自白 终章
《幽默报 10》
AFO 有感
OI 之旅
《幽默报》
[Works] 自白
[Idea] 试卷排序
其他物件杂物收纳
Hitokoto

Yurchiu 说，除了她以外的人都很强！嘤嘤嘤~~
博客信息
文章数目
158
最近更新
08-21
本站字数
350.6k
文章目录

©2019-2023 Yurchiu. All rights reserved.

Theme Cutie, by Yurchiu.