记录编号	596123	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	猴猴吃苹果	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.776 s
提交时间	2024-10-22 14:24:32	内存使用	5.22 MiB

#include<bits/stdc++.h>
using namespace std;  
const int MAXN = 50010;  
vector<int> g[MAXN];  
int de[MAXN], fa[MAXN], son[MAXN];  
int deq[MAXN], yz;  
bool v[MAXN];  
void add(int a, int b) {  
    g[a].emplace_back(b);  
    g[b].emplace_back(a);  
}  
void dfs(int node, int par) {  
    fa[node] = par;  
    de[node] = (par == -1) ? 0 : de[par] + 1;  
    bool isson = true;  
    for (int neighbor : g[node]) {  
        if (neighbor != par) {  
            isson = false;  
            dfs(neighbor, node);  
        }  
    }  

    if (isson) {  
        son[++yz] = node;
    }  
}  
bool deCom(int a, int b) {  
    if (de[a] != de[b])  
        return de[a] > de[b];  
    return a < b;  
}  
bool sumCom(int a, int b) {  
    if (deq[a] != deq[b])  
        return deq[a] > deq[b];  
    return a < b;  
}  
int main(){  
    freopen("apple.in","r",stdin);
    freopen("apple.out","w",stdout);
    int n, k;  
    cin >> n >> k;  
    for (int i = 1; i < n; ++i) {  
        int x,y;  
        cin >> x>>y;  
        add(y, x);
    }  
    yz = 0;  
    dfs(k, -1); 
    sort(son + 1, son + 1 + yz, deCom);  
    v[k] = true;  
    for (int i = 1; i <= yz; ++i) {  
        int cur = son[i];  
        while (!v[cur]) {  
            ++deq[son[i]];  
            v[cur] = true;  
            cur = fa[cur];  
        }  
    }  
    sort(son + 1, son + 1 + yz, sumCom);  
    cout << k << endl;  
    for (int i = 1; i <= yz; ++i) {  
        cout << son[i] << endl;  
    }  
    return 0;  
}