比赛 |
20241022 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
猴猴吃苹果 |
最终得分 |
100 |
用户昵称 |
darkMoon |
运行时间 |
0.474 s |
代码语言 |
C++ |
内存使用 |
5.88 MiB |
提交时间 |
2024-10-22 09:56:36 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto IN = freopen("apple.in", "r", stdin);
auto OUT = freopen("apple.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 5e4 + 5;
int n = mread(), k = mread(), son[N], f[N], e[N], idx, la[N];
vector<int> v[N];
pair<int, int> p[N];
void dfs1(int x, int fa){
f[x] = 1;
int ma = 0, p = 0;
la[x] = x;
for(int y : v[x]){
if(y == fa){
continue;
}
dfs1(y, x);
if(f[y] == ma){
if(la[y] < la[p]){
p = y;
}
}
if(f[y] > ma){
ma = f[y];
p = y;
}
}
f[x] = f[p] + 1;
son[x] = p;
if(son[x] != 0){
la[x] = la[son[x]];
}
return;
}
void dfs2(int x, int fa){
e[son[x]] = 1;
if(e[x] == 0){
p[++idx] = mp(-f[x], la[x]);
}
for(int y : v[x]){
if(y == fa){
continue;
}
dfs2(y, x);
}
return;
}
signed main(){
for(int i = 1, x, y; i < n; i ++){
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs1(k, 0);
dfs2(k, 0);
sort(p + 1, p + 1 + idx);
printf("%lld\n", k);
for(int i = 1; i <= idx; i ++){
printf("%lld\n", p[i].se);
}
return 0;
}