fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1e4 + 5;
  10. int c, n, k, cur, dp[N];
  11. int h[N], cnt[N], sz[N];
  12. vector <int> adj[N], g[N], ans;
  13.  
  14. void nhap() {
  15.     cin >> c >> n >> k;
  16.     FOR(i, 2, n) {
  17.         int u, v; cin >> u >> v;
  18.         adj[u].push_back(v);
  19.         adj[v].push_back(u);
  20.     }
  21. }
  22.  
  23. void dfs(int u, int p = -1) {
  24.     sz[u] = 1;
  25.     ++cnt[h[u]];
  26.  
  27.     for (int v : adj[u]) if (v != p) {
  28.         h[v] = h[u] + 1;
  29.         dfs(v, u);
  30.         sz[u] += sz[v];
  31.         g[u].push_back(v);
  32.     }
  33. }
  34.  
  35. void bfs(int u) {
  36.     sz[u] = (h[u] == cur);
  37.     for (int v : g[u]) {
  38.         bfs(v);
  39.         sz[u] += sz[v];
  40.     }
  41. }
  42.  
  43. void calc(int u) {
  44.     if ((c == 1 && dp[k - h[u] + 1]) || (c == 2 && dp[k - 1] && h[u] == cur)) ans.push_back(u);
  45.     for (int v : g[u]) if (sz[v]) FORD(i, n, sz[v]) dp[i] += dp[i - sz[v]];
  46.     for (int v : g[u]) {
  47.         if (sz[v]) FOR(i, sz[v], n) dp[i] -= dp[i - sz[v]];
  48.         calc(v);
  49.         if (sz[v]) FORD(i, n, sz[v]) dp[i] += dp[i - sz[v]];
  50.     }
  51.     for (int v : g[u]) if (sz[v]) FOR(i, sz[v], n) dp[i] -= dp[i - sz[v]];
  52. }
  53.  
  54. void giai() {
  55.     h[1] = 1;
  56.     dfs(1);
  57.  
  58.     dp[1] = 1;
  59.     if (c == 2) {
  60.         FOR(i, 1, n) {
  61.             cnt[i] += cnt[i - 1];
  62.             if (cnt[i] >= k) {
  63.                 cur = i;
  64.                 break;
  65.             }
  66.         }
  67.  
  68.         bfs(1);
  69.         k -= cnt[cur - 1];
  70.         dp[1] = 0;
  71.         dp[0] = 1;
  72.     }
  73.     calc(1);
  74.  
  75.     sort(ans.begin(), ans.end());
  76.     for (int x : ans) cout << x << ' ';
  77. }
  78.  
  79. int main() {
  80.     ios_base::sync_with_stdio(0);
  81.     cin.tie(0); cout.tie(0);
  82.  
  83.     #define name "test"
  84.  
  85.     if (fopen(name".inp", "r")) {
  86.         freopen(name".inp", "r", stdin);
  87.         freopen(name".out", "w", stdout);
  88.     }
  89.  
  90.     nhap();
  91.     giai();
  92.  
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Gh9csg
language:
C++14 (clang 8.0)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!