http://poj.openjudge.cn/practice/C26G/

#include <bits/stdc++.h>
using namespace std;

int query(vector<int> S);

int leaf(int n) {
    // 题目通常保证 n >= 2。
    // n == 2 时两个点都是叶子。
    if (n <= 2) return 1;

    vector<int> cur(n);
    iota(cur.begin(), cur.end(), 1);

    vector<int> mark(n + 1, 0);
    int timer = 0;

    auto calcF = [&](const vector<int>& S) -> int {
        int cS;

        if ((int)S.size() == 1) {
            cS = 1;
        } else {
            cS = query(S);
        }

        ++timer;
        for (int x : S) mark[x] = timer;

        vector<int> comp;
        comp.reserve(n - S.size());

        for (int i = 1; i <= n; i++) {
            if (mark[i] != timer) {
                comp.push_back(i);
            }
        }

        int cComp;
        if ((int)comp.size() == 1) {
            cComp = 1;
        } else {
            cComp = query(comp);
        }

        return cS - cComp + 1;
    };

    while ((int)cur.size() > 1) {
        int m = (int)cur.size() / 2;

        vector<int> A(cur.begin(), cur.begin() + m);

        int fA = calcF(A);

        if (fA > 0) {
            cur.swap(A);
        } else {
            vector<int> B(cur.begin() + m, cur.end());
            cur.swap(B);
        }
    }

    return cur[0];
}