fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. const int N = 200200;
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8. vector < int > v[N];
  9.  
  10. int ask(int x)
  11. {
  12.         int y;
  13.         printf("1 %d\n", x);
  14.         fflush(stdout);
  15.         scanf("%d", &y);
  16.         return y;
  17. }
  18.  
  19. int s[N];
  20. bool dead[N];
  21.  
  22. void dfs(int x, int p = -1)
  23. {
  24.         s[x] = 1;
  25.         for(int y: v[x]){
  26.                 if(y == p || dead[y]){
  27.                         continue;
  28.                 }
  29.                 dfs(y, x);
  30.                 s[x] += s[y];
  31.         }
  32. }
  33.  
  34. int get_centroid(int x, int sz, int p = -1)
  35. {
  36.         int mx = sz - s[x];
  37.         for(int y: v[x]){
  38.                 if(y == p || dead[y]) {
  39.                         continue;
  40.                 }
  41.                 int g = get_centroid(y, sz, x);
  42.                 if(g != -1){
  43.                         return g;
  44.                 }
  45.                 mx = max(mx, s[y]);
  46.         }
  47.         if(mx <= sz / 2){
  48.                 return x;
  49.         }
  50.         return -1;
  51. }
  52.  
  53. int get(int x)
  54. {
  55.         dfs(x);
  56.         x = get_centroid(x, s[x]);
  57.         dead[x] = true;
  58.         dfs(x);
  59.  
  60.         int y = ask(x);
  61.         assert(!dead[y]);
  62.         if(y == -1){
  63.                 return x;
  64.         } else{
  65.                 return get(y);
  66.         }
  67. }
  68.  
  69. void solve()
  70. {
  71.         scanf("%d", &n);
  72.         for(int i = 1; i <= n; i++){
  73.                 v[i].clear();
  74.                 dead[i] = 0;
  75.         }
  76.         for(int i = 1; i < n; i++){
  77.                 int x, y;
  78.                 scanf("%d%d", &x, &y);
  79.                 v[x].push_back(y);
  80.                 v[y].push_back(x);
  81.         }
  82.  
  83.         int res = get(1);
  84.  
  85.         printf("2 %d\n", res);
  86.         fflush(stdout);
  87.         scanf("%d", &res);
  88. }
  89.  
  90. int main()
  91. {
  92.         //freopen("Btree.txt", "r", stdin);
  93.         //freopen("output.txt", "w", stdout);
  94.         ios_base::sync_with_stdio(0);
  95.  
  96.         int T;
  97.         scanf("%d", &T);
  98.         while(T--){
  99.                 solve();
  100.         }
  101. }
Success #stdin #stdout 0s 20904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Lk8N2x
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!