比赛 NOIP2025模拟赛1 评测结果 EEEEEEAEEE
题目名称 路径覆盖 最终得分 10
用户昵称 李奇文 运行时间 1.360 s
代码语言 C++ 内存使用 7.65 MiB
提交时间 2025-11-24 12:04:52
显示代码纯文本
#include<bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int n,q,d[N];
vector<int>e[N];
vector<unordered_map<int,int>> dso;
int dfs(int u,int fa){
    int p=(d[u]%2!=0)?1:0;
    for(int v:e[u]){
        if(v==fa) continue;
        int sump=dfs(v,u);
        dso[u][v]=sump;
        p+=sump; 
    }
    return p;
}
int main(){
	freopen("lucover.in","r",stdin);
	freopen("lucover.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
		d[x]++;d[y]++;
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		if(d[i]>1){
			sum++;
		}
	}
	if(sum==1){
		for(int i=1;i<=q;i++){
			int x;
			cin>>x;
			if(d[x]>1){
				cout<<1<<"\n";
			}else{
				cout<<(n-2)/2+1+((n-2)%2==0?0:1)<<"\n";
			}
		}
		return 0;
	}
	dfs(1,-1);
	for(int i=1;i<=q;i++){
		int p,ans=0;
		cin>>p;
		for(int j:e[p]){
			ans+=dso[p][j];
		}
		cout<<(ans>>1)+1<<"\n";
	}
	return 0;
}