100pts求调玄关
查看原帖
100pts求调玄关
1037502
luxiaomao楼主2024/5/25 16:01

知道是要求 lca 到根的最大值,但是还是被卡了。

#include<bits/stdc++.h>
#define N 100005
using namespace std;

int n,q;

struct edge{int v,nex;}e[2*N];
int tot,head[N];
void add(int u,int v){e[++tot].v = v,e[tot].nex = head[u],head[u] = tot;}

int lg[N],dis[N],a[N],fa[N][30];
void init(){for(int i = 1;i <= n;i++)lg[i] = lg[i-1] + (1<<lg[i-1]==i);}
void dfs(int las,int u,int maxx)
{
	dis[u] = dis[las] + 1;
	if(u > maxx)maxx = u;a[u] = maxx;
	fa[u][0] = las;
	for(int i = 1;i <= lg[u];i++)
		fa[u][i] = fa[fa[u][i-1]][i-1];
	for(int i = head[u];i;i = e[i].nex)
		if(e[i].v != las)dfs(u,e[i].v,maxx);
}
int lca(int u,int v)
{
	if(dis[u] < dis[v])swap(u,v);
	while(dis[u] > dis[v])u = fa[u][lg[dis[u]-dis[v]]-1];
	if(u == v)return u;
	for(int i = lg[dis[u]]-1;i+1;i--)
		if(fa[u][i] != fa[v][i])u = fa[u][i],v = fa[v][i];
	return fa[u][0];
}

int main()
{
	scanf("%d",&n);
	for(int i = 1;i < n;i++)
	{
		int x;
		scanf("%d",&x);
		add(i,x),add(x,i);
	}
	init(),dfs(0,0,0);
	scanf("%d",&q);
	while(q--)
	{
		int m,u,v;
		scanf("%d%d",&m,&u);
		for(int i = 2;i <= m;i++)
			scanf("%d",&v),u = lca(u,v);
		printf("%d\n",a[u]);
	}
	return 0;
}
2024/5/25 16:01
加载中...