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