71792024-01-01 20:35:43anonUtazási irodacpp17Accepted 45/45118ms47128 KiB
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
using namespace std;
ll dfs(ll v, ll lst, vector<ll> &ccs, const vector<set<ll>> &tree) {
    for(const auto &x : tree[v]) {
        if(x != lst)
            ccs[v] += dfs(x, v, ccs, tree);
    }
    return ccs[v];
}
int main() {
    FastIO;
    ll i, u, v, sn, N, K;
    cin >> N >> K;
    vector<set<ll>> tree(N + 1);
    for(i = 1; i < N; i++) {
        cin >> u >> v;
        tree[u].insert(v);
        tree[v].insert(u);
    }
    sn = (K / N) + 1;
    K = K % N;
    vector<ll> ccs(N + 1, 1);
    dfs(sn, 0, ccs, tree);
    u = 0;
    stack<ll> st;
    st.push(sn);
    while(!st.empty() && K) {
        v = st.top();
        st.pop();
        cout << v << ' ';
        K--;
        if(!K)
            break;
        for(const auto &x : tree[v]) {
            if(x == u)
                continue;
            if(K > ccs[x])
                K -= ccs[x];
            else {
                st.push(x);
                break;
            }
        }
        u = v;
    }
    cout << '\n';
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base45/45
1Accepted0/03ms1828 KiB
2Accepted0/09ms5560 KiB
3Accepted2/23ms2392 KiB
4Accepted2/23ms2600 KiB
5Accepted1/13ms2824 KiB
6Accepted2/24ms3552 KiB
7Accepted2/24ms3760 KiB
8Accepted1/14ms3948 KiB
9Accepted2/279ms45568 KiB
10Accepted2/281ms46240 KiB
11Accepted1/1103ms47128 KiB
12Accepted2/283ms33172 KiB
13Accepted2/298ms32780 KiB
14Accepted2/278ms33692 KiB
15Accepted2/297ms33380 KiB
16Accepted2/2118ms33252 KiB
17Accepted3/375ms33988 KiB
18Accepted2/290ms33472 KiB
19Accepted2/275ms33596 KiB
20Accepted2/272ms34116 KiB
21Accepted3/375ms33472 KiB
22Accepted3/374ms33600 KiB
23Accepted3/375ms34120 KiB
24Accepted1/181ms34248 KiB
25Accepted1/175ms35160 KiB