求助
查看原帖
求助
742017
zhangxiao666楼主2023/5/21 16:50

全WA,求调

#include<bits/stdc++.h>
using namespace std;
int n,k,h;
vector<int> a[5001]; 
int b[5001];
int p[5001];
int c[501];
int eat[5001];
int t[5001];
int o[5001];
int f[5001];
int pos[5001];
void dfs1(int now,int fa)
{
	int mp,mt;
	if(p[now])
	{
		mp=p[now];
		mt=0;
	}
	else 
	{
		mp=100000;
		mt=100000;
	}
	for(int i=0;i<a[now].size();i++)
	{
		int to=a[now][i];
		if(to==fa) continue;
		dfs1(to,now);
		if(t[to]+1<mt||(t[to]+1==mt&&to<mp))
		{
			mt=t[to]+1;
			mp=to;
		}
	}
	t[now]=mt;
	o[now]=mp;
}
void dfs2(int now,int fa)
{
	if(o[now]!=100000)
	{
		if(f[o[now]]==-1&&o[fa]!=o[now])
		{
			int mt=min(t[fa],t[now]);
			f[o[now]]=min(f[o[fa]],mt);
		}
		if(f[o[now]]!=-1&&f[o[now]]==t[now]) pos[o[now]]=now;
	}
	for(int i=0;i<a[now].size();i++)
	{
		if(a[now][i]==fa) continue;
		dfs2(a[now][i],now);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
	{
		int x;
		scanf("%d",&x);
		p[x]=i;
		b[i]=x;
	}
	scanf("%d",&h);
	for(int i=1;i<=h;i++)
	{
		scanf("%d",&c[i]);
	}
	for(int i=1;i<=h;i++)
	{
		memset(t,0,sizeof(t));
		memset(o,0,sizeof(o));
		memset(f,-1,sizeof(f));
		dfs1(c[i],-1);	
		eat[o[c[i]]]++;
		f[o[c[i]]]=t[c[i]];
		dfs2(c[i],-1);
		memset(p,0,sizeof(p));
		for(int j=1;j<=k;j++)
		{
			b[j]=pos[j];
			p[b[j]]=j;
		}
	}
	for(int i=1;i<=k;i++)
	{
		printf("%d %d\n",b[i],eat[i]);
	}
	return 0;
}
2023/5/21 16:50
加载中...