100分WA求调(你就看看这题有多少100WA的吧)
查看原帖
100分WA求调(你就看看这题有多少100WA的吧)
1435579
PYC201401楼主2025/6/27 19:57

本蒟蒻第一次发帖,如有不合适内容请指出,将修改

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> g[100005];
int dep[100005],t[100005],box[100005],f[100005];
bool vis[100005];
int root;
void dfs(int cur,int step)
{
	vis[cur]=true;
	dep[cur]=step;
	box[dep[cur]]++;
	for (auto i:g[cur])
	{
		if (i!=0&&!vis[i])dfs(i,step+1);
	}
}
int lca(int u,int v)
{
	while(u!=v)
	{
		if (dep[u]>dep[v])u=f[u];
		else v=f[v];
	}
	return u;
}
int q;
int main()
{
	cin>>n;
	for (int i=1;i<n;i++)
	{
		cin>>f[i];
		g[i].push_back(f[i]);
		g[f[i]].push_back(i);
	}
	
	dfs(0,1);
	cin>>q;
	while(q--)
	{
		int m;
		cin>>m;
		int r=0;
		for (int i=1;i<=m;i++)
		{
			int t;
			cin>>t;
			if (i==1)r=t;
			else r=lca(r,t);
		}
		cout<<r<<endl;
	}
	return 0;
}

在小猴编程提交已AC,但洛谷提交过不了HACK数据求帮 小猴编程传送门

2025/6/27 19:57
加载中...