比赛 NOIP2025模拟赛1 评测结果 AAWWWTWWTT
题目名称 路径覆盖 最终得分 20
用户昵称 郑霁桓 运行时间 3.861 s
代码语言 C++ 内存使用 7.40 MiB
提交时间 2025-11-24 12:28:41
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,q,xx,yy,ss,dp[100005][2],dg[100005],ps,pp,tp,p1,p2;
vector<int>v[100005];
inline void dfs(int x,int fa){
	dp[x][1]=1;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==fa) continue;
		dfs(v[x][i],x);
		dp[x][1]+=dp[v[x][i]][0];
	}
	dp[x][0]=1e9;
	for(int i=0;i<(1<<(v[x].size()));i++){
		ps=pp=tp=0;
		for(int j=0;j<v[x].size();j++){
			if(v[x][j]==fa) continue; 
			ps+=dp[v[x][j]][(i>>j)&1];
			if(((i>>j)&1)==0){
				if(v[v[x][j]].size()>1) pp++;
				else tp++;
			}
		}
		if(tp<pp){
			pp-=tp;
		}else tp-=pp;
		dp[x][0]=min(dp[x][0],ps-pp/2+(tp+1)/2);
	}
	return;
}
int main(){
	freopen("lucover.in","r",stdin);
	freopen("lucover.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<n;i++){
		cin>>xx>>yy;
		v[xx].push_back(yy);
		v[yy].push_back(xx);
		dg[xx]++;
		dg[yy]++;
	}
	for(int i=1;i<=n;i++){
		if(dg[i]>1){
			p1++;
		}
		if(dg[i]==2){
			p2++;
		}
	}
	if(p1==1){
		for(int i=1;i<=n;i++) if(dg[i]>1) p1=i;
		while(q--){
			cin>>xx;
			if(xx==p1){
				cout<<"1\n";
			}else{
				cout<<(n-1)/2<<"\n";
			}
		}
		return 0;
	}
	if(p1==p2){
		for(int i=1;i<=n;i++) if(dg[i]==1){
			if(p1) p2=i;
			else p1=i;
		}
		while(q--){
			cin>>xx;
			if(xx==p1||xx==p2||xx==v[p1][0]||xx==v[p2][0]){
				if(n==2) cout<<"1\n";
				else cout<<"2\n";
			}else{
				if(n==3) cout<<"1\n";
				cout<<"3\n";
			}
		}
		return 0;
	}
	while(q--){
		cin>>xx;
		ss=0;
		for(int i=1;i<=n;i++) dp[i][0]=dp[i][1]=0;
		for(int i=0;i<v[xx].size();i++){
			dfs(v[xx][i],xx);
			ss+=dp[v[xx][i]][0];
		}
		cout<<ss+1<<"\n"; 
	}
	return 0;
}