社区讨论

后5个点re了找不到问题

P3379【模板】最近公共祖先(LCA)参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@loblt9pa
此快照首次捕获于
2023/10/29 23:06
2 年前
此快照最后确认于
2023/11/04 03:58
2 年前
查看原帖
rt,采用st表优化欧拉 代码部分
CPP
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
int head[MAXN],oula[MAXN*4],numc,num[MAXN*2],fath[MAXN*2],re[MAXN*2],fir_oula[MAXN*2];
int lg[MAXN*2],maxn[MAXN][50];
struct stu{
	int next,to;
}sd[MAXN*2];
int cnt;
void dfs_mk(int x,int fa)
{
	num[x]=++numc;
	re[num[x]]=x;
	fath[x]=fa;
	for(int i=head[x];i;i=sd[i].next)
		if(sd[i].to-fa)
			dfs_mk(sd[i].to,x);
	return;
}
void dfs_bk(int x)
{
	if(fath[x])
		oula[++numc]=num[fath[x]];
	return;
}
void dfs_fr(int x)
{
	oula[++numc]=num[x];
	for(int i=head[x];i;i=sd[i].next)
		if(sd[i].to-fath[x])
		{
			dfs_fr(sd[i].to);
			dfs_bk(sd[i].to);
		}
	return;
}
void get_fir_oula()
{
	for(int i=1;i<=numc;i++)
		if(!fir_oula[oula[i]])
			fir_oula[oula[i]]=i;
	return;
}
signed main()
{
	//freopen("P3379_8.in","r",stdin);
	int n,m,s;
	cin>>n>>m>>s;
	int tmpx,tmpy;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&tmpx,&tmpy);
		for(int j=0;j<2;j++)
		{
			sd[++cnt].next=head[tmpx];
			sd[cnt].to=tmpy;
			head[tmpx]=cnt;
			swap(tmpx,tmpy);
		}
	}
	dfs_mk(s,0);
	numc=0;
	dfs_fr(s);
	lg[0]--;
	for(int i=1;i<=numc;i++)
		lg[i]=lg[i>>1]+1;
	for(int i=1;i<=numc;i++)
		maxn[i][0]=oula[i];
	for(int i=1;i<=lg[numc];i++)
        for(int j=1;j+(1<<i)-1<=numc;j++)
            maxn[j][i]=min(maxn[j][i-1],maxn[j+(1<<i-1)][i-1]);
    get_fir_oula();
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&tmpx,&tmpy);
		int ntmpx=fir_oula[num[tmpx]],ntmpy=fir_oula[num[tmpy]];
		if(ntmpx>ntmpy)
			swap(ntmpx,ntmpy);
		int mid=lg[ntmpy-ntmpx+1];
		printf("%d\n",re[min(maxn[ntmpx][mid],maxn[ntmpy-(1<<(mid))+1][mid])]);
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...