CodeForces-1305D Kuroni and the Celebration

传送门：CodeForces-1305D

题目描述

给你一个树，每次询问两个点，返回这两个点的LCA，最多询问n/2次，找出根节点

思路分析

就是一个删除叶子节点的过程：
将边数为1的点，放进队列，每次取出两个点询问
如果LCA是其中一个，那就是根
如果不是，就将这两个点删除，并更新想连的点的边数，为1的进队列

样例输入

6
1 4
4 2
5 3
6 3
2 3

3

4

4

样例输出

? 5 6

? 3 1

? 1 2

! 4

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

vector<int>e[N];
int deg[N];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif

    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    queue<int>q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1)
            q.push(i);
    int time = n / 2;
    while (!q.empty() && time--) {
        int r1 = q.front();
        q.pop();
        int r2 = q.front();
        q.pop();
        cout << "? " << r1 << " " << r2 << endl;
        int root;
        cin >> root;
        if (root == r1 || root == r2) {
            cout << "! " << root << endl;
            return 0;
        }
        deg[r1] = -1;
        deg[r2] = -1;
        for (auto v : e[r1]) {
            deg[v]--;
            if (deg[v] == 1)
                q.push(v);
        }
        for (auto v : e[r2]) {
            deg[v]--;
            if (deg[v] == 1)
                q.push(v);
        }
    }

    for (int i = 1; i <= n; i++)
        if (!deg[i])
            cout << "! " << i << endl;

    return 0;
}
&nbsp;