社区讨论
hack数据WA,玄关求调ing
P10113[GESP202312 八级] 大量的工作沟通参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mdfc7sqj
- 此快照首次捕获于
- 2025/07/23 10:21 8 个月前
- 此快照最后确认于
- 2025/11/04 03:54 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
vector<int> G[N];
int fa[N][21], dep[N];
void dfs(int x, int f) {
fa[x][0] = f;
dep[x] = dep[f] + 1;
for(int i=1; i<=20; i++)
fa[x][i] = fa[fa[x][i-1]][i-1];
for(int v : G[x])
if(v != f) dfs(v, x);
}
int LCA(int x, int v) {
if(dep[x] < dep[v]) swap(x,v);
for(int i=20; i>=0; i--)
if(dep[fa[x][i]] >= dep[v])
x = fa[x][i];
if(x == v) return x;
for(int i=20; i>=0; i--)
if(fa[x][i] != fa[v][i])
x=fa[x][i], v=fa[v][i];
return fa[x][0];
}
int main() {
int n, m;
cin >> n;
for(int i=1; i<n; i++) {
int p;
cin >> p;
G[p].push_back(i);
G[i].push_back(p);
}
dfs(0, -1);
cin >> m;
while(m--) {
int k, x, v;
cin >> k >> x;
for(int i=1; i<k; i++) {
cin >> v;
x = LCA(x, v);
}
cout << x << endl;
}
return 0;
}
膜拜叨佬orz
回复
共 1 条回复,欢迎继续交流。
正在加载回复...