CodeForces Round 680 E 解法

定义：每条边均标记一个正整数数值 $e_i$ ，若这些数值均满足以下条件，我们说这棵树满足性质 $\bf{X}$ ：

条件：每两个标记有相同数值 $a$ 的边的路径（边 $a\leftrightarrow b$ 到边 $c\leftrightarrow d$ 的路径指 $a\Leftrightarrow c$ 、 $a\Leftrightarrow d$ 、 $b\Leftrightarrow c$ 、 $b\Leftrightarrow d$ 这几条路径中最短的一条）所经过的边上所有的数值中最大的数值要超过 $a$ 。

推论：满足性质 $\bf{X} \Leftrightarrow$ 存在一个最坏情况下消耗的时间不超过 $\max e_i$ 的解。

证明：找到数值最大的边（由 $\bf{X}$ 可知必只有一条），先询问它，根据结果选择其中一端递归（递归的树同样满足 $\bf{X}$ ，且 $\max e_i$ 至少比原树小一）即可。 $\blacksquare$

推论：满足性质 $\bf{X}$ 且 $\max e_i$ 最小解即为所求。

下面，对于一个以 $v$ 为根的树而言：

定义：一条边可见为 $v$ 到这条边的路径（边 $a\leftrightarrow b$ 到点 $c$ 的路径指 $a\Leftrightarrow c$ 、 $b\Leftrightarrow c$ 中最短的一条）上的所有边中数值最大的边的数值小于这条边的数值。

推论：这棵树满足性质 $\bf{X} \Leftrightarrow$ 所有子树（拆掉点 $v$ 后形成的森林）都满足 $\bf{X}$ 且可见边的数值均不同。

定义：这样一棵树的势为 $\sum 2^{c_i}$ ，其中 $c_i$ 为每条可见边的数值。

推论：对于这棵树，性质 $\bf{X}$ 且势最小即为所求。

推论：求势最小是可以用子树DP的。

证明：

假设所有子树的最小解均已求出，那么补上余下的边（与 $v$ 相邻的边）的数值相当于，把每棵子树(对应的这条边补上的数值为 $x$ )小于 $x$ 的可见边变成不可见，再加上一条数值为 $x$ 的可见边，然后再要满足各个子树的可见边数值交起来没重叠，同时我们要保证这样操作后总的势最小。

这恰好对应于每棵子树的势都变大（合法的变大不是任意的，但是任意变大后总的势最小解恰为合法变大后总的势最小解），然后所有势加起来时没有进位（看作一个二进制数，没有进位），同时要保证这样操作后总的势最小。（这样一个子问题 $\bf Z$ ，具体表述见下）

这样假设存在整体最优解中某棵子树并不最优，那么它的势更大，对应的子问题 $\bf Z$ 限制更紧，解必不优于这棵子树选用最优解。

所以这里是满足最优子结构可以进行子树DP的。 $\blacksquare$

定义：子问题 $\bf Z$ 为给定一个大二进制数值的数组 $\{a_i\}$ ，求一个数组 $\{b_i\}$ ，使得 $b_i > a_i$ 并且 $\{b_i\}$ 的和最小，同时 $\{b_i\}$ 求和时（二进制加法）没有进位。

推论：记该问题解决所需时间复杂度为 $T(n)$ ，那么，总时间复杂度 $\mathcal O(n T(n))$ ，原题解说存在 $T(n)=\mathcal O(n^3)$ 的简单实现与 $T(n)=\mathcal O(n\log n)$ 版本的实现（但是提交几乎都是 $\mathcal O(n^3)$ 或 $\mathcal O(n^2\log n)$ 的实现）。

算法：

解决子问题 $\bf Z$ 的方法：

首先，最终的和肯定不会超过一个足够大的全 $1$ 数字，将其记作 $z$ 。

尝试 $z$ 的从高到低每一位分别变成 $0$ ，可以就变，不可以就不变，这样下来可得到最下的 $z$ 。

可行与否的判定方法：

尝试把 $z$ 中的每一位分配（从高到低分配）给所有子树势集合中当前的最大数（分配后数可能消失，可能对应位置 $0$ ，但分配完后必须每个数字都消失）。 $\blacksquare$

实现提示：由于 $2\leq n\leq 100$ ，上文提到的大二进制数值可用 __int128 存储（注意在 Codeforces 上选择 $64$ 位语言提交）。

实现：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    const int N = 105;
    static vector<int> E[N];
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        E[x].push_back(y);
        E[y].push_back(x);
    }
    typedef __int128 sl;
    static int pa[N], sz[N], rk[N];
    function<sl(int, int)> dfs = [&](int u, int p) -> sl {
        pa[u] = p;
        vector<pair<sl, int>> pos;
        sz[u] = 1;
        for (int v : E[u])
            if (v != p) pos.emplace_back(dfs(v, u), v), sz[u] += sz[v];
        if (pos.empty()) return 0;
        int n = sz[u] - 1;
        auto check = [&](sl v) -> bool {
            priority_queue<pair<sl, int>> queue;
            for (auto &po : pos)
                queue.push(po);
            for (int i = n - 1; i >= 0; i--)
                if (v >> i & 1) {
                    if (queue.empty()) return true;
                    auto& top = queue.top();
                    sl x = sl(1) << i;
                    sl y = top.first;
                    int z = top.second;
                    queue.pop();
                    if (x <= y) {
                        if (!(y & x)) return false;
                        y ^= x;
                        queue.emplace(y, z);
                    }
                    rk[z] = i;
                }
            return queue.empty();
        };
        sl po = (sl(1) << n) - 1;
        int cur = n - 1;
        while (cur >= 0) {
            if (check(po ^ (sl(1) << cur))) po ^= (sl(1) << cur);
            cur--;
        }
        assert(check(po));
        return po;
    };
    dfs(1, 0);
    rk[1] = -1;
    auto cut_edge = [&](int x, int y) {
        E[x].erase(find(E[x].begin(), E[x].end(), y));
        E[y].erase(find(E[y].begin(), E[y].end(), x));
    };
    typedef pair<int, int> rk_t;
    auto get_rk = [&](int x, int y) -> rk_t {
        if (pa[x] == y) return {rk[x], x};
        else return {rk[y], y};
    };
    function<rk_t(int, int)> dfs_max = [&](int u, int p) -> rk_t {
        rk_t mn = get_rk(u, p);
        for (int v : E[u])
            if (v != p) mn = max(dfs_max(v, u), mn);
        return mn;
    };
    int cur = 1;
    while (E[cur].size()) {
        rk_t rk_val = dfs_max(cur, 0);
        cut_edge(rk_val.second, pa[rk_val.second]);
        printf("? %d %d\n", rk_val.second, pa[rk_val.second]);
        fflush(stdout);
        scanf("%d", &cur);
    }
    printf("! %d\n", cur);
    return 0;
}