https://codeforces.com/contest/1174/problem/F

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
vector<int> v[maxn],h;
int sz[maxn],dep[maxn],depx;
//sz数组存储以i为根节点的树拥有多少结点(包括i本身)
int pre(int node,int p){
    sz[node]=1;
    for(int u:v[node]){
        if(u!=p){
            dep[u]=dep[node]+1;
            sz[node]+=pre(u,node);
        }
    }
    return sz[node];
}

int query(char c,int u){
    printf("%c %d\n",c,u);
    fflush(stdout);
    int ans;
    scanf("%d",&ans);
    return ans;
}

void get(int node){
    h.push_back(node);
    int big=-1;
    for(int u:v[node]){
        if(sz[node]>sz[u]&&(big==-1||(sz[u]>sz[big])))
            big=u;
    }
    if(big!=-1) get(big);
}

int dfs(int node){
    h.clear();
    get(node);
    int depy=(depx+dep[h.back()]-query('d',h.back()))/2,y=h[depy-dep[node]];
    if (depx==depy)
    return y;
    return dfs(query('s',y));
}

int main(){
    //freopen("datain.txt", "r", stdin);
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    depx=query('d',1);
    pre(1,0);
    printf("! %d\n",dfs(1));
    fflush(stdout);
}