Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 212345;
- int marc[MAXN], sub[MAXN];
- vector <int> grafo[MAXN];
- void dfs1(int v, int p) {
- //printf("%d\n", v);
- sub[v] = 1;
- for(int i = 0; i < grafo[v].size(); i++) {
- int viz = grafo[v][i];
- if(marc[viz] == 1 || viz == p) continue;
- dfs1(viz, v);
- sub[v] += sub[viz];
- }
- }
- int dfs(int v, int p, int a) {
- for(int i = 0; i < grafo[v].size(); i++) {
- int viz = grafo[v][i];
- if(marc[viz] == 1 || viz == p) continue;
- if(sub[viz] >= a) {
- return dfs(viz, v, a);
- }
- }
- return v;
- }
- int main() {
- int n;
- scanf("%d", &n);
- for(int i = 0; i < n - 1; i++) {
- int a, b;
- scanf("%d %d", &a, &b);
- grafo[a].push_back(b); grafo[b].push_back(a);
- }
- int at = 1;
- int cn;
- int cnt = 0;
- while(true) {
- if(cnt == 36) return 0;
- dfs1(at, at);
- //printf("%d\n", sub[at]);
- cn = dfs(at, at, (sub[at]) /2);
- marc[cn] = 1;
- printf("? 2 %d\n", cn);
- cnt++;
- fflush(stdout);
- scanf("%d", &at);
- if(at == 0) break;
- }
- printf("! %d\n", cn);
- fflush(stdout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement