比赛 NOIP2025模拟赛1 评测结果 AAWWWWAAWW
题目名称 路径覆盖 最终得分 40
用户昵称 梦那边的美好TE 运行时间 0.165 s
代码语言 C++ 内存使用 4.15 MiB
提交时间 2025-11-24 11:33:29
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+10;
int n,d[N],q,cnt,mx,u[N],v[N];
int main(){
	freopen("lucover.in","r",stdin);
	freopen("lucover.out","w",stdout);
	scanf("%d %d",&n,&q);
	for(int i=1;i<n;i++){
		scanf("%d %d",u+i,v+i);
		d[u[i]]++,d[v[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(d[i]>1)cnt++,mx=d[i];
	}
	if(cnt>1){
		int a,b;
		for(int i=1;i<=n;i++){
			if(d[i]==1)swap(a,b),a=i;
		}
		for(int i=1;i<n;i++){
			if(u[i]==a||u[i]==b)d[v[i]]=1;
			if(v[i]==a||v[i]==b)d[u[i]]=1;
		}
	}
	while(q--){
		int x;
		scanf("%d",&x);
		if(cnt==1){
			// 菊花 
			if(d[x]>1)printf("1\n");
			else printf("%d\n",mx/2+1);
		}else{
			// 链 
			if(d[x]==1)printf("2\n");
			else printf("3\n");
		}
	}
	return 0;
}