比赛 NOIP2025模拟赛1 评测结果 WWWWWWTTTT
题目名称 路径覆盖 最终得分 0
用户昵称 会挽弯弓满月 运行时间 4.564 s
代码语言 C++ 内存使用 4.79 MiB
提交时间 2025-11-24 11:58:10
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<48||c>57){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57){
		x=(x<<1)+(x<<3)+c-48;
		c=getchar();
	}
	return f*x;
}
int n,Q;
int d[N];
struct edge{
	int to,nxt;
}e[N<<1];
int h[N],tot;
void add(int u,int v){
	e[++tot]={v,h[u]};
	h[u]=tot;
}
vector<int> leaf;
int way[N],fa[N];
//0:无
//1:操作二过了
//2:无法使用操作二 
void init(int x){
	for(int i=1;i<=n;i++){
		way[i]=0;
		fa[i]=0;
	}
	int v;
	for(int i=h[x];i;i=e[i].nxt){
		v=e[i].to;
		way[v]=2;
	}
}
void bfs(int x){
	queue<int> q;
	q.push(x);
	int u,v;
	while(q.size()){
		u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			v=e[i].to;
			if(v==fa[u]) continue;
			fa[v]=u;
			q.push(v);
		}
	}
}
void solve(int x){
	queue<int> q;
	bool vis[N]={0};
	for(int i=0;i<leaf.size();i++){
		if(leaf[i]==x) continue;
		q.push(leaf[i]);
		vis[leaf[i]]=1;
	}
	int u,v,ans=1;
	while(q.size()){
		u=q.front();q.pop();
		v=fa[u];
		if(v==x) continue;
		if(way[v]==1||way[u]==1) continue;
		ans++;
		if(way[v]==0){
			way[v]=1;
			if(way[fa[v]]!=1) way[fa[v]]=2;
		}
		if(vis[v]==0){
			vis[v]=1;
			q.push(v);
		}
	}
	printf("%d\n",ans);
}
int main(){
	freopen("lucover.in","r",stdin);
	freopen("lucover.out","w",stdout);
	n=read();Q=read();
	int u,v,x;
	for(int i=1;i<n;i++){
		u=read();v=read();
		add(u,v);add(v,u);
		d[u]++;d[v]++;
	}
	for(int i=1;i<=n;i++)
		if(d[i]==1) leaf.push_back(i);
	while(Q--){
		x=read();
		init(x);
		bfs(x);
		solve(x);
	}
	return 0;
}
/*
10 10
1 2
2 3
2 4
1 5
5 6
5 7
7 8
7 9
7 10
*/