SHARE
TWEET

Untitled

a guest Jun 3rd, 2019 445 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. bool del[200005];
  5. vector<int> v[200005];
  6. int par[200005],sz[200005],dep[200005],depx;
  7. void pre(int node,int p)
  8. {
  9.     for (int u:v[node])
  10.     {
  11.         if (u!=p)
  12.         {
  13.             par[u]=node;
  14.             dep[u]=dep[node]+1;
  15.             pre(u,node);
  16.         }
  17.     }
  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. int getsz(int node,int p)
  29. {
  30.     sz[node]=1;
  31.     for (int u:v[node])
  32.     {
  33.         if (!del[u] && u!=p)
  34.         sz[node]+=getsz(u,node);
  35.     }
  36.     return sz[node];
  37. }
  38. int find(int node,int p,int nn)
  39. {
  40.     for (int u:v[node])
  41.     {
  42.         if (!del[u] && u!=p && sz[u]>nn/2)
  43.         return find(u,node,nn);
  44.     }
  45.     return node;
  46. }
  47. int dfs(int node)
  48. {
  49.     getsz(node,0);
  50.     int c=find(node,0,sz[node]),d=query('d',c);
  51.     if (!d)
  52.     return c;
  53.     del[c]=1;
  54.     if (dep[c]+d==depx)
  55.     return dfs(query('s',c));
  56.     return dfs(par[c]);
  57. }
  58. int main()
  59. {
  60.     int n;
  61.     scanf("%d",&n);
  62.     for (int i=1;i<n;i++)
  63.     {
  64.         int a,b;
  65.         scanf("%d%d",&a,&b);
  66.         v[a].push_back(b);
  67.         v[b].push_back(a);
  68.     }
  69.     depx=query('d',1);
  70.     pre(1,0);
  71.     printf("! %d\n",dfs(1));
  72.     fflush(stdout);
  73. }
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