fast_turtle

Untitled

Dec 8th, 2022
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 212345;
  4. int marc[MAXN], sub[MAXN];
  5. vector <int> grafo[MAXN];
  6. void dfs1(int v, int p) {
  7.     //printf("%d\n", v);
  8.     sub[v] = 1;
  9.     for(int i = 0; i < grafo[v].size(); i++) {
  10.         int viz = grafo[v][i];
  11.         if(marc[viz] == 1 || viz == p) continue;
  12.         dfs1(viz, v);
  13.         sub[v] += sub[viz];
  14.     }
  15. }
  16. int dfs(int v, int p, int a) {
  17.     for(int i = 0; i < grafo[v].size(); i++) {
  18.         int viz = grafo[v][i];
  19.         if(marc[viz] == 1 || viz == p) continue;
  20.         if(sub[viz] >= a) {
  21.             return dfs(viz, v, a);
  22.         }
  23.     }
  24.     return v;
  25. }
  26. int main() {
  27.     int n;
  28.     scanf("%d", &n);
  29.     for(int i = 0; i < n - 1; i++) {
  30.         int a, b;
  31.         scanf("%d %d", &a, &b);
  32.         grafo[a].push_back(b); grafo[b].push_back(a);
  33.     }
  34.     int at = 1;
  35.     int cn;
  36.     int cnt = 0;
  37.     while(true) {
  38.         if(cnt == 36) return 0;
  39.         dfs1(at, at);
  40.         //printf("%d\n", sub[at]);
  41.         cn = dfs(at, at, (sub[at]) /2);
  42.         marc[cn] = 1;
  43.         printf("? 2 %d\n", cn);
  44.         cnt++;
  45.         fflush(stdout);
  46.         scanf("%d", &at);
  47.         if(at == 0) break;
  48.     }
  49.     printf("! %d\n", cn);
  50.     fflush(stdout);
  51.     return 0;
  52. }
  53.  
Add Comment
Please, Sign In to add comment