题解 P6541 【[WC2018]即时战略】

· · 题解

学OI一年半，终于切了第一道交互题。

简述题意

有一棵有标号的树，n个点，1为根，初始只有1已知。你可以调用一个explore(x, y)函数，其中x为已知点，y为未知点，函数会返回从x往y走的下一个点。限制你调用explore的次数大约为n \log n次，你需要猜出整颗树的结构。

解法

首先我们有一个很显然的暴力思路。

对于每一个未知的点，我们从1开始调用explore，一直走到这个点。

由于树的深度最坏是O(n)的，所以每找一个新点需要的时间也是O(n)，总复杂度是O(n ^ 2)。

考虑减小每次达到新点的复杂度，也就是减小“深度”，不难想到可以利用点分治的性质，即点分治深度为O(\log n)。

维护已知树的点分树，从点分根节点开始，设当前所在节点为x，想找到y的位置，令z=explore(x, y)，那么我们从z往上爬点分父亲，一直爬到x，就可以用O(\log n)的复杂度知道z在x的哪个点分子树内。我们跳到这个点分儿子，继续重复前面的操作，一直到找到y从哪伸出去就可以了。这样，我们每寻找一个y节点，时间复杂度是O(\log ^ 2 n)，explore的调用次数是O(\log n)。

现在我们的问题是，如何给点分树动态加点。我们每次先默认新加点的点分父亲是原树父亲，从这个点往上爬点分父亲，找到最后一个点分子树大小超过点分父亲点分子树大小0.7倍的点x，把以x的点分父亲为根的点分子树所对应的联通块重新构建点分树即可。（说的好绕

对于这道题，我们需要特别注意一下链的情况，允许的调用次数是O(n + \log n)的。对于这种情况，我们把寻找节点的次序random_shuffle一下。令已知链的左端点为l，右端点为r，目标点为y，z=explore(l, y)，如果z未知，就从z向y推，反之从r向y推。这样，把n个点全部找出来，期望的“失败”次数是O(\log n)的。

代码

#include <bits/stdc++.h>
//#include "rts.h"
#define MAXN _________

using namespace std;
const int MAXN = 1e6 + 5;

int n, a[MAXN], vis[MAXN], fini[MAXN];
int explore(int, int);
// int explore(int x, int y) {}
// int main() {}

void WorkLine() {
    srand(time(0));
    for (int i = 1; i < n; i++) a[i] = i + 1;
    random_shuffle(a + 1, a + n);
    int l = 1, r = 1;
    fini[1] = 1;
    for (int i = 1; i < n; i++) {
        int ter = a[i];
        if (fini[ter]) continue;
        int x = explore(l, ter), now = 0;
        if (fini[x]) now = r, r = ter;
        else fini[x] = 1, now = x, l = ter;
        while (!fini[ter]) now = explore(now, ter), fini[now] = 1;
    }
}

int to[MAXN], nx[MAXN], head[MAXN], ecnt;
int dfa[MAXN], ddep[MAXN], dsiz[MAXN], maxw[MAXN], siz[MAXN];
int nowrt;

void Add(int x, int y) {
    to[++ecnt] = y; nx[ecnt] = head[x]; head[x] = ecnt;
    to[++ecnt] = x; nx[ecnt] = head[y]; head[y] = ecnt;
}

int Find(int u, int fa, int tot) {
    siz[u] = 1;
    maxw[u] = 0;
    int res = 0;
    for (int i = head[u]; i; i = nx[i]) {
        int v = to[i];
        if (vis[v] || v == fa) continue;
        int cen = Find(v, u, tot);
        if (!res || maxw[cen] < maxw[res]) res = cen;
        maxw[u] = max(maxw[u], siz[v]);
        siz[u] += siz[v];
    }
    maxw[u] = max(maxw[u], tot - siz[u]);
    if (!res || maxw[u] < maxw[res]) res = u;
    return res;
}

void Divide(int u, int tot) {
    vis[u] = 1;
    for (int i = head[u]; i; i = nx[i]) {
        int v = to[i];
        if (vis[v]) continue;
        int subs = (siz[v] < siz[u] ? siz[v] : tot - siz[u]);
        int subc = Find(v, u, subs);
        dfa[subc] = u;
        ddep[subc] = ddep[u] + 1;
        dsiz[subc] = subs;
        Divide(subc, subs);
    }
}

void Clear(int u, int fa, int lim) {
    dfa[u] = 0;
    ddep[u] = 0;
    dsiz[u] = 0;
    vis[u] = 0;
    for (int i = head[u]; i; i = nx[i]) {
        int v = to[i];
        if (v == fa || ddep[v] < lim) continue;
        Clear(v, u, lim);
    }
};

void Rebuild(int u) {
    int tot = dsiz[u];
    int fa = dfa[u];
    int depth = ddep[u];
    Clear(u, 0, depth);
    int cen = Find(u, 0, tot);
    if (u == nowrt) nowrt = cen;
    dfa[cen] = fa;
    ddep[cen] = depth;
    dsiz[cen] = tot;
    Divide(cen, tot);
}

void Update(int now) {
    int reb = 0;
    while (dfa[now]) {
        if (1.0 * dsiz[now] > 0.7 * dsiz[dfa[now]]) reb = dfa[now];
        now = dfa[now];
    }
    if (reb) Rebuild(reb);
}

void Reach(int ter) {
    int now = nowrt;
    while (!fini[ter]) {
        int nex = explore(now, ter);
        if (!fini[nex]) {
            Add(now, nex);
            dfa[nex] = now;
            ddep[nex] = ddep[now] + 1;
            vis[nex] = 1;
            fini[nex] = 1;
            dsiz[nex] = 0;
            for (int cur = nex; cur; cur = dfa[cur]) dsiz[cur]++;
            now = nex;
            Update(now);
        } else {
            int son = nex;
            while (dfa[son] != now) son = dfa[son];
            now = son;
        }
    }
}

void Work() {
    srand(time(0));
    for (int i = 1; i < n; i++) a[i] = i + 1;
    random_shuffle(a + 1, a + n);
    fini[1] = 1;
    ddep[1] = 1;
    vis[1] = 1;
    dsiz[1] = 1;
    nowrt = 1;
    for (int i = 1; i < n; i++) {
        int ter = a[i];
        if (fini[ter]) continue;
        Reach(ter);
    }
}

void play(int n, int T, int dataType) {
    ::n = n;
    if (dataType == 3) WorkLine();
    else Work();
}