社区讨论
后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 条回复,欢迎继续交流。
正在加载回复...