- 工作沟通6级T2 2023.12
- @ 2026-08-23 22:50:51
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 500005
int n,m,q,dep[MAXN],p[MAXN][22],hum[MAXN],mx[MAXN];
vector<int> g[MAXN];
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
p[u][0]=fa;
for (int i=1;i<=20;i++)
p[u][i]=p[p[u][i-1]][i-1];
for (int i=0;i<g[u].size();i++)
if (g[u][i]!=fa)
mx[g[u][i]]=max(mx[u],g[u][i]),dfs(g[u][i],u);
}
bool cmp (int a,int b)
{
return dep[a]<dep[b];
}
int lca()
{
sort(hum+1,hum+m+1,cmp);
for (int i=20;i>=0;i--)
for (int j=2;j<=m;j++)
if (dep[p[hum[j]][i]]>=dep[hum[1]])
hum[j]=p[hum[j]][i];
int ok=1;
for (int j=2;j<=m;j++)
if (hum[j-1]!=hum[j])
{
ok=0;break;
}
if (ok) return mx[hum[1]];
for (int i=20;i>=0;i--)
{
ok=0;
for (int j=2;j<=m;j++)
if (p[hum[j]][i]!=p[hum[1]][i])
{
ok=1;break;
}
if (ok)
for (int j=1;j<=m;j++) hum[j]=p[hum[j]][i];
}
return mx[p[hum[1]][0]];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for (int i=1;i<=n-1;i++)
{
int v;
cin>>v;
g[i].push_back(v);
g[v].push_back(i);
}
dfs(0,0);
cin>>q;
while(q--)
{
cin>>m;
for (int i=1;i<=m;i++) cin>>hum[i];
cout<<lca()<<endl;
}
return 0;
}
洛谷ac,但是vijos拿不满
0 条评论
目前还没有评论...
信息
- ID
- 2564
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 89
- 已通过
- 3
- 通过率
- 3%
- 上传者