fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const int maxn = 1e4 + 10;
  6. const int mod = 1e9 + 7;
  7.  
  8. int c , n , k;
  9. int sz[maxn] , dp[maxn] , depth[maxn] , mp[maxn] , now;
  10. vector<int>adj[maxn] , g[maxn], ans;
  11.  
  12. int get_sizes (int u = 1 , int p = 0, int d = 1){
  13.     depth[u] = d;
  14.     mp[d]++;
  15.     for(int v : adj[u]){
  16.         if(v != p){
  17.             sz[u] += get_sizes(v , u , d + 1);
  18.             g[u].push_back(v);
  19.         }
  20.     }
  21.     return ++sz[u];
  22. }
  23.  
  24. int get_sizes2 (int u = 1){
  25.     sz[u] = (depth[u] == now);
  26.     for(int v : g[u])
  27.         sz[u] += get_sizes2(v);
  28.     return sz[u];
  29. }
  30.  
  31. void dfs (int u = 1){
  32.     if((c == 1 && dp[k - depth[u] + 1]) || (c == 2 && dp[k - 1] &&  depth[u] == now)) ans.push_back(u);
  33.     for(int v : g[u]){
  34.         if(sz[v]){
  35.             for(int i = n; i >= sz[v]; --i) dp[i] += dp[i - sz[v]];
  36.         }
  37.     }
  38.     for(int v : g[u]){
  39.         if(sz[v]){
  40.             for(int i = sz[v]; i <= n; ++i) dp[i] -= dp[i - sz[v]];
  41.         }
  42.         dfs(v);
  43.         if(sz[v]){
  44.             for(int i = n; i >= sz[v]; --i) dp[i] += dp[i - sz[v]];
  45.         }
  46.     }
  47.     for(int v : g[u]){
  48.         if(sz[v]){
  49.             for(int i = sz[v]; i <= n; ++i) dp[i] -= dp[i - sz[v]];
  50.         }
  51.     }
  52. }
  53.  
  54.  
  55. void solve(){
  56.     cin >> c >> n >> k;
  57.     for(int i = 1; i < n; ++i){
  58.         int u , v; cin >> u >> v;
  59.         adj[u].push_back(v);
  60.         adj[v].push_back(u);
  61.     }
  62.     get_sizes();
  63.     dp[1] = 1;
  64.     if(c == 2){
  65.         for(int i = 1 ; i <= n; ++i){
  66.             mp[i] += mp[i - 1];
  67. //            cout << mp[i] << ' ';
  68.             if(mp[i] >= k){
  69.                 now = i;
  70.                 break;
  71.             }
  72.         }
  73.         get_sizes2();
  74.         k -= mp[now - 1];
  75.         dp[1] = 0;
  76.         dp[0] = 1;
  77.     }
  78.     dfs();
  79.     sort(ans.begin() , ans.end());
  80.     for(auto x : ans) cout << x << ' ';
  81. }
  82.  
  83. int main(){
  84.     ios_base::sync_with_stdio(0);
  85.     cin.tie(0);
  86.     cout.tie(0);
  87.     int t = 1;
  88.     // cin >> t;
  89.     while(t--) solve();
  90. }
  91.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4xOPSj
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!