| 比赛 |
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;
}