1 条题解
-
1
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=200005; int n,m,k,s,t,Q,f[N][21],de[N],d[N],mx[N]; queue<int> q; vector<int> e[N]; void dfs(int u){ for (int v:e[u]){ if (v!=f[u][0]){ f[v][0]=u; de[v]=de[u]+1; mx[v]=max(v,mx[u]); dfs(v); } } } int lca(int u,int v){ if (de[u]<de[v]) swap(u,v); for (int k=de[u]-de[v],o=0;k;k>>=1,++o) if (k&1) u=f[u][o]; if (u==v) return u; for (int j=20;j>=0;--j) if (f[u][j]!=f[v][j]) u=f[u][j],v=f[v][j]; return f[u][0]; } int main(){ freopen("in.txt","r",stdin); cin>>n; for (int i=2;i<=n;++i){ cin>>s;s++; e[s].push_back(i); } mx[1]=1; dfs(1); for (int j=1;j<=20;++j) for (int i=1;i<=n;++i) f[i][j]=f[f[i][j-1]][j-1]; cin>>Q; int u,v; while (Q--){ cin>>k; int p; for (int i=1;i<=k;++i){ cin>>s;s++; if (i==1) p=s; else p=lca(p,s); } cout<<mx[p]-1<<"\n"; } }
- 1
信息
- ID
- 788
- 时间
- 2000ms
- 内存
- 500MiB
- 难度
- 10
- 标签
- 递交数
- 7
- 已通过
- 0
- 上传者