| 比赛 |
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
*/