SHARE
TWEET

Untitled

a guest Jun 3rd, 2019 529 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. vector<int> v[200005];
  5. int sz[200005],dep[200005],depx;
  6. int pre(int node,int p)
  7. {
  8.     sz[node]=1;
  9.     for (int u:v[node])
  10.     {
  11.         if (u!=p)
  12.         {
  13.             dep[u]=dep[node]+1;
  14.             sz[node]+=pre(u,node);
  15.         }
  16.     }
  17.     return sz[node];
  18. }
  19. vector<int> h;
  20. int query(char c,int u)
  21. {
  22.     printf("%c %d\n",c,u);
  23.     fflush(stdout);
  24.     int ans;
  25.     scanf("%d",&ans);
  26.     return ans;
  27. }
  28. void get(int node)
  29. {
  30.     h.push_back(node);
  31.     int big=-1;
  32.     for (int u:v[node])
  33.     {
  34.         if (sz[node]>sz[u] && (big==-1 || (sz[u]>sz[big])))
  35.         big=u;
  36.     }
  37.     if (big!=-1)
  38.     get(big);
  39. }
  40. int dfs(int node)
  41. {
  42.     h.clear();
  43.     get(node);
  44.     int depy=(depx+dep[h.back()]-query('d',h.back()))/2,y=h[depy-dep[node]];
  45.     if (depx==depy)
  46.     return y;
  47.     return dfs(query('s',y));
  48. }
  49. int main()
  50. {
  51.     int n;
  52.     scanf("%d",&n);
  53.     for (int i=1;i<n;i++)
  54.     {
  55.         int a,b;
  56.         scanf("%d%d",&a,&b);
  57.         v[a].push_back(b);
  58.         v[b].push_back(a);
  59.     }
  60.     depx=query('d',1);
  61.     pre(1,0);
  62.     printf("! %d\n",dfs(1));
  63.     fflush(stdout);
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top