100pts Unaccepted求调
查看原帖
100pts Unaccepted求调
1016866
dlzlj_2010楼主2024/3/27 12:26
#include<bits/stdc++.h>
using namespace std;
const int N=500005;

vector<int>vec[N];
//记录每个结点可以走向哪些结点 
int f[N*2][21],mem[N*2][21],depth[N*2],first[N],vis[N*2],lg[N];
//f:记录深度序列区间中的最小深度
//mem:记录 找到深度序列区间中的最小深度 时的对应结点(在欧拉序列中) 
//depth:在dfs过程中记录遍历到每个点时的对应深度
//first:记录每个结点第一次出现时在欧拉序列中的位置
//vis:欧拉序列
//lg;lg[i]==log_{2}{i}+1 
int cnt=0,n,m;
//cnt:每走到一个点计一次数
 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
} 
 
void dfs(int now,int dep)
{
	if(!first[now]) 
		first[now]=++cnt;//第一次遍历到该点 
		
	depth[cnt]=dep,vis[cnt]=now;
	for(int i=0;i<vec[now].size();i++)
	{
		if(first[vec[now][i]]) 
			continue;//是该结点的父节点,跳过 
		else 
			dfs(vec[now][i],dep+1);
		++cnt;
		depth[cnt]=dep,vis[cnt]=now;//深搜完了vec[now][i]下的分支,回到当前结点 now
	}
}
 
void ST()
{
	for(int i=1;i<=cnt;i++)
	{
		lg[i]=lg[i-1]+((1<<lg[i-1])==i);
		f[i][0]=depth[i];//区间长度为1时,该区间内深度的最小值就是该结点的深度 
		mem[i][0]=vis[i];
	}
	for(int j=1;(1<<j)<=cnt;j++)//枚举的区间长度倍增 
		for(int i=1;i+(1<<j)-1<=cnt;i++)//枚举合法的每个区间起点 
		{
			if(f[i][j-1]<f[i+(1<<(j-1))][j-1])//深度最小的点在前半个区间 
			{
				f[i][j]=f[i][j-1];
				mem[i][j]=mem[i][j-1];
			}
			else//深度最小的后半个区间 
			{
				f[i][j]=f[i+(1<<(j-1))][j-1];
				mem[i][j]=mem[i+(1<<(j-1))][j-1];
			}
		}
}
 
int LCA(int x,int y)
{
	int l=first[x],r=first[y];//找到输入的两个结点编号对应在欧拉序列中第一次出现的位置 
	if(l>r) 
		swap(l,r);
	int k=lg[r-l+1]-1;
	if(f[l][k]<f[r-(1<<k)+1][k]) 
		return mem[l][k];
	else 
		return mem[r-(1<<k)+1][k];
}
 
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int a;
		a=read();
		vec[a].push_back(i);
		vec[i].push_back(a);
	}
	dfs(0,0);//打表,给first、depth、vis赋值,给RMQ奠定基础 
	
	ST();//打表,给f和mem赋值 ,给ST奠定基础 
	int q=read();
    while(q--){
        int p,p1;
        cin>>m>>p;
        for(int i=2;i<=m;++i){
            cin>>p1;
            p=LCA(p,p1);
        }
        int ans=p;
        while(p){
            ans=max(ans,f[p][0]);
            p=f[p][0];
        }
        cout<<ans<<'\n';
    }

	return 0;
}
2024/3/27 12:26
加载中...