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