- 答疑
【最优首都选择】
- 2025-10-2 22:23:52 @
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct DATA {
int u, v; // u向v
}edge[200005];
vector <int> a[200006];
int dp[200006];
void dfs1(int p, int f) {
dp[p] = 0;
for (int i : a[p]) {
int v= edge[i].u ^ edge[i].v ^ p;
if(v == f) continue;
// if (i == f) continue;
dfs1(v,p);
dp[p] += dp[v];
if (p == edge[i].v) dp[p]++;
}
}
void dfs2(int p, int f, int edge_i) {
if ( f != 0) {
// for (int i : a[p]) {
// if (p == edge[edge_i].v) dfs2(edge[i].u, p, i);
// else dfs2(edge[i].v, p, i);
// }
// return ;
if( p == edge[edge_i].v){
dp[p] = dp[f] + 1;
}else{
dp[p] = dp[f] - 1;
}
}
for(int i :a[p]){
// int v=
int v= edge[i].u ^ edge[i].v ^ p;
if(v == f) continue;
dfs2(v,p,i);
}
// if (p == edge[edge_i].v) dp[p] = dp[f] + 1;
// else dp[p] = dp[f] - 1;
// for (int i : a[p]) {
// if (i == f) continue;
// if (p == edge[edge_i].v) dfs2(edge[i].u, p, i);
// else dfs2(edge[i].v, p, i);
// }
}
int main() {
int n; cin >> n;
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
edge[i].u = u; edge[i].v = v;
a[u].push_back(i); a[v].push_back(i);
}
dfs1(1, 0);
dfs2(1, 0, 0);
// int mini = n+1;
int min_v = n +1;
for (int i = 1; i <= n; i++) {
// if (dp[i] < dp[mini]) mini = i;
min_v = min(min_v,dp[i]);
}
// cout << dp[mini] << endl;
cout<<min_v<<endl;
// for (int i = 1; i <= n; i++) {
// if (dp[i] == dp[mini]) cout << i << ' ';
// }
vector<int> res;
for(int i = 1;i<=n;++i){
if(dp[i] == min_v){
res.push_back(i);
}
}
for(int i = 0;i<res.size();i++){
cout<<res[i] <<(i == res.size() - 1 ? "" : " ");
}
//
// int maxi = 0;
// for (int i = 1; i <= n; i++) {
// if (dp[i] > dp[maxi]) maxi = i;
// }
//
// cout << maxi - 1 << endl << dp[maxi] << endl;
return 0;
}
0 条评论
目前还没有评论...
YIZHIYANG 一只羊 LV 9
推荐阅读