P11517 [CCO 2024] Infiltration

给出一棵节点数为 $n$ 的无根树，有两个人 A & B 位于这棵树上，且不知道对方的位置。

在时刻为奇数时 A 可以选择不动，或者移动到相邻节点；在时刻为偶数时 B 可以选择不动，或者移动到相邻节点。

你需要为两个人各自制定 $n$ 个策略，第 $i$ 个策略代表这个人初始位于节点 $i$ 时，接下来 $T$ 个时刻内的移动策略。要求 $T \le 1440$。

记 $d(u,v)$ 为 $u,v$ 两点间距离，$t(u,v)$ 为 A 从 $u$ 出发且 B 从 $v$ 出发，按照策略两人第一次相遇的时刻。你需要使

$$S=\max_{u=1}^n \max_{v=1}^n \dfrac{t(u,v)}{d(u,v)}$$

尽可能小。输出构造。

$n \le 100$，满分要求 $S \le 15$，1 秒，2048 MB。

首先，两人的地位是相同的，因此策略也应该相同，不能向子树里乱跑。于是有一个平凡构造：任意定根后，两人不断跳父亲，此时 $S=2n$，可以获得 24pts。

我们要最小化比值，应该让距离小的 $(u,v)$ 相遇的时刻较小，距离大的 $(u,v)$ 相遇的时刻较大，可以考虑倍增。令 A & B 不断跳 $2^0,2^1,2^2,\cdots,2^7$ 步，此时 $S$ 被压缩到 $\log n$ 级别，且 $T$ 为 $n \log n$ 级别。朴素的实现中，$S \approx 17.27$，可以获得 80pts。

接下来是卡常环节。先引入第一个优化：选择树的中心定根。这里 $n$ 很小，直接 $O(n^2)$ 找中心即可，这样 $100$ 的最大深度被压到 $50$，可以得到 88pts。

然后引入第二个优化：每次跳的步数不必须为 $2$ 的幂次，考虑类似百万富翁那样乱搞一组步数序列。经过搜索和人力调参，取步数序列 $1,2,5,14,28,43,60,80$ 可以通过本题数据。最大的 $S=14.6$。

const int N = 105;
const int num[8] = {1, 2, 5, 14, 28, 43, 60, 80};
int n, fa[N], dep[N];
vector<int> e[N], a[N], b[N];
void dfs1(int u, int fa) {
    for (int v : e[u]) {
        if (v == fa) continue;
        dep[v] = dep[u] + 1, dfs1(v, u);
    }
}
void dfs2(int u) {
    for (int v : e[u]) {
        if (v == fa[u]) continue;
        fa[v] = u, dfs2(v);
    }
}

void _main() {
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    dfs1(0, -1);
    int rt = 0, md = *max_element(dep, dep + n);
    for (int i = 1; i < n; i++) {
        dep[i] = 0, dfs1(i, -1); 
        int cd = *max_element(dep, dep + n);
        if (cd < md) rt = i, md = cd;
    }
    fa[rt] = rt, dfs2(rt);
    const int m = 1024;
    cout << m << '\n';
    for (int u = 0; u < n; u++) {
        int c = 0, p = u, l = 1, len = 2 * num[0], idx = 0;
        for (int t = 1; t <= m; t++) {
            if (t >= l + len) {
                l += len, idx++, c ^= 1;
                if (idx < 8) len = 2 * num[idx];
            }
            if (c == 0 && t % 2 == 1) p = fa[p];
            cout << p << ' ';
        }
        cout << '\n';
    }
    for (int u = 0; u < n; u++) {
        int c = 0, p = u, l = 1, len = 2 * num[0], idx = 0;
        for (int t = 1; t <= m; t++) {
            if (t >= l + len) {
                l += len, idx++, c ^= 1;
                if (idx < 8) len = 2 * num[idx];
            }
            if (c == 1 && t % 2 == 0) p = fa[p];
            cout << p << ' ';
        }
        cout << '\n';
    }
}