Advertisement
fast_turtle

Untitled

Dec 8th, 2022
27
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement