20分求助
查看原帖
20分求助
1020927
gujiahon_g楼主2024/4/26 23:17

样例过了

#include<bits/stdc++.h>
using namespace std;
int k,n,head[10005],sweet,tot,first[100005],dis[10005],cnt[10005],on[10005],node[10005],a,b,h;//dis[i]表示第i个节点离根距离,on[i]表示第i个贪吃虫当前的位置,node[i]表示第i个节点当前的贪吃虫编号(node[i]=0表示当前节点没有贪吃虫) 
struct bian{
	int from,to,nxt;
}e[10005];
void add(int a,int b){
	e[++tot]={a,b,head[a]};
	head[a]=tot;
}//链式前向星 
void dfs1(int x,int fa){
	if(node[x]){
		first[node[x]]=dis[x];
	}
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to!=fa){
			dis[to]=dis[x]+1;//因为这是一棵树所以每个节点只会搜到一次,我就直接更新了 
			dfs1(to,x);
		}
	}
}
void dfs(int x,int fa,bool flag){//x表示当前dfs搜到的节点编号,fa表示上一个节点编号,避免重复搜,flag表示该路线上是否有离根更近的贪吃虫 
	vector<int> v;//用来记录有贪吃虫的子节点编号 
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to!=fa){
			dfs(to,x,flag&&(!node[x]));//如果此时node[x]不为0,则以x为根的树上的贪吃虫也不会移动 
			if(node[to]){
				v.push_back(to);
			}
		}
	}if(node[x]||(!flag)){//若此处有贪吃虫,它的子节点上的贪吃虫就不会移动 
		return ;
	}int min1=2e9,minid=2e9,minnode=0;//min1表示v中dis的最小值,minid表示应该移动的贪吃虫不会,minnode表示该移动的贪吃虫所在的节点的编号 
	for(auto it:v){
		if(first[node[it]]<min1){
			min1=first[node[it]];
			minnode=it;
			minid=node[it];
		}else if(first[node[it]]==min1&&node[it]<minid){
			min1=first[node[it]];
			minnode=it;
			minid=node[it];
		}
	}if(minnode){//如果minnode=0说明子节点上没有贪吃虫,不需要做任何操作 
		node[x]=node[minnode];
		node[minnode]=0;
		on[minid]=x;//将应该移动的贪吃虫移动到x 
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);//链接ab,这里应该是无向图 
	}scanf("%d",&k);
	for(int i=1;i<=k;i++){
		scanf("%d",&on[i]);
		node[on[i]]=i;//初始化 
	}scanf("%d",&h);
	for(int i=1;i<=h;i++){
		scanf("%d",&sweet);
		memset(dis,0,sizeof(dis));//因为每次的根不同,所以清空了dis 
		memset(first,0,sizeof(first));
		dis[sweet]=1;
		dfs1(sweet,-1);
		dfs(sweet,-1,1);
		cnt[node[sweet]]++;
	}for(int i=1;i<=k;i++){
		printf("%d %d\n",on[i],cnt[i]);
	}
}
2024/4/26 23:17
加载中...