专栏文章

题解：P11516 [CCO 2024] Summer Driving

hhhoppitreeMadeline
P11516题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqcqy3u
此快照首次捕获于
2025/12/04 02:40
3 个月前
此快照最后确认于
2025/12/04 02:40
3 个月前
查看原文
简单数据结构优化 dp。
首先特判 A≤BA\le B，否则以 rtrt 为根，记 fxf_x 表示 xx 到根的路径被 ban 了，现在在 xx，Alice 先手的最大值，gx(x≠rt)g_x(x\ne rt) 表示 xx 到根的路径被 ban 了，现在在 faxfa_x，Alice 先手的最大值。
转移可以枚举 Alice 的策略，均摊复杂度是对的，考虑快速计算此时 Bob 的策略，相当于一个链上查询和一个大小为 BB 的邻域查询（但是要扣除到根的路径，用两个数据结构维护即可。
扣除的具体方法为：在点分树上，如果分治中心非这个点的祖先，那么不用考虑，否则，另外一个点不能为分治中心的祖先；并且另一个点不能与此点位于同一个分治中心划分出的子树内。所以，开两棵动态开点线段树，一棵维护具有祖先关系的点，一棵维护其它点，并且每个节点上要维护最优的值以及所属子树，以及其它子树中的次优值，查询时判断取二者中的哪个即可。
以下是 483483 行的代码，可能有大多重复内容。
参考代码：
CPP
#include <bits/stdc++.h>

using namespace std;

char I[22000038], *J = I;

inline int read() {
    unsigned int x = 0;
    while (*J < 48 || 57 < *J) ++J;
    while (47 < *J && *J < 58) x = (x << 1) + (x << 3) + (*J++ ^ 48);
    return x;
}

const int N = 3e5 + 5;

vector<int> G[N];
int n, rt, oa, ob, dep[N], Fa[N], tFa[N];
vector<int> S, hv[N];

void dfs(int x, int fa = -1) {
    if ((int)S.size() >= oa) {
        hv[S[S.size() - oa]].push_back(x);
    }
    if ((int)S.size() >= ob) {
        Fa[x] = S[S.size() - ob];
    }
    if ((int)S.size() >= ob - 1) {
        if (ob != 1) tFa[x] = S[S.size() - (ob - 1)];
        else tFa[x] = x;
    }
    S.push_back(x);
    for (auto v : G[x]) {
        if (v != fa) {
            dep[v] = dep[x] + 1, dfs(v, x);
        }
    }
    S.pop_back();
}

int fa[N], siz[N], son[N], top[N], dfn[N];

void dfs1(int x) {
    siz[x] = 1;
    for (auto v : G[x]) {
        if (v == fa[x]) continue;
        fa[v] = x;
        dfs1(v);
        siz[x] += siz[v];
        if (siz[v] > siz[son[x]]) {
            son[x] = v;
        }
    }
}

void dfs2(int x) {
    dfn[x] = ++dfn[0];
    if (!son[x]) return;
    top[son[x]] = top[x];
    dfs2(son[x]);
    for (auto v : G[x]) {
        if (v == fa[x] || v == son[x]) continue;
        top[v] = v;
        dfs2(v);
    }
}

int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            swap(x, y);
        }
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

int getLst(int x, int y) {
    while (x) {
        if (fa[top[x]] == y) return top[x];
        x = fa[top[x]];
    }
    return son[y];
}

namespace DS1 {
    int mn[1 << 20], lz[1 << 20];

    void build(int k, int l, int r) {
        mn[k] = lz[k] = 1e9;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
    }

    void Init() {
        build(1, 1, n);
    }

    void pushdown(int k) {
        if (lz[k] != 1e9) {
            mn[k << 1] = min(mn[k << 1], lz[k]);
            lz[k << 1] = min(lz[k << 1], lz[k]);
            mn[k << 1 | 1] = min(mn[k << 1 | 1], lz[k]);
            lz[k << 1 | 1] = min(lz[k << 1 | 1], lz[k]);
            lz[k] = 1e9;
        }
    }

    void modify(int k, int l, int r, int x, int y, int v) {
        if (l > y || r < x) return;
        if (l >= x && r <= y) {
            mn[k] = min(mn[k], v);
            lz[k] = min(lz[k], v);
            return;
        }
        pushdown(k);
        int mid = (l + r) >> 1;
        modify(k << 1, l, mid, x, y, v);
        modify(k << 1 | 1, mid + 1, r, x, y, v);
        mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
    }

    void modify(int x, int y, int v) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) {
                swap(x, y);
            }
            modify(1, 1, n, dfn[top[x]], dfn[x], v);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) {
            swap(x, y);
        }
        modify(1, 1, n, dfn[x], dfn[y], v);
    }

    int query(int k, int l, int r, int x) {
        if (l == r) return mn[k];
        pushdown(k);
        int mid = (l + r) >> 1;
        if (x <= mid) return query(k << 1, l, mid, x);
        return query(k << 1 | 1, mid + 1, r, x);
    }
}

int anc(int x, int y) {
    return (dfn[y] >= dfn[x] && dfn[y] <= dfn[x] + siz[x] - 1);
}

namespace DS2 {
    vector< pair<int, int> > pts;
    int vis[N], tsiz[N], Rt;

    void dfsRt(int x, int fa = -1) {
        tsiz[x] = 1;
        int flg = 1;
        for (auto v : G[x]) {
            if (vis[v] || v == fa) continue;
            dfsRt(v, x);
            tsiz[x] += tsiz[v];
            flg &= (tsiz[v] * 2 <= tsiz[0]);
        }
        if (!Rt && flg && (tsiz[0] - tsiz[x]) * 2 <= tsiz[0]) {
            Rt = x;
        }
    }

    int getRt(int x) {
        tsiz[0] = tsiz[x];
        Rt = 0;
        dfsRt(x), dfsRt(Rt);
        return Rt;
    }

    int tfa[N], tdep[N], _SZ[N], mxDis;
    vector<int> T[N];
    int dis[20][N], col[20][N];

    void getInfo(int x, int id, int fa = -1) {
        mxDis = max(mxDis, dis[id][x] + 1);
        for (auto v : G[x]) {
            if (vis[v] || v == fa) continue;
            dis[id][v] = dis[id][x] + 1;
            col[id][v] = (col[id][x] ? col[id][x] : v);
            getInfo(v, id, x);
        }
    }

    void build(int x, int fat) {
        tfa[x] = fat, T[fat].push_back(x);
        vis[x] = 1;
        mxDis = 0, getInfo(x, tdep[x]), _SZ[x] = mxDis;
        for (auto v : G[x]) {
            if (!vis[v]) {
                int w = getRt(v);
                tdep[w] = tdep[x] + 1;
                build(w, x);
            }
        }
    }

    void initDS();

    void Init() {
        tsiz[1] = n;
        int trt = getRt(1);
        tdep[trt] = 1;
        build(trt, 0);
        initDS();
    }

    struct node {
        int l, r, v, wh, sec;
    } p[N << 7];

    int tot;

    void modify(int &k, int l, int r, int x, int y, int z) {
        if (!k) {
            k = ++tot;
            p[k].v = y, p[k].wh = z, p[k].sec = 1e9;
        } else {
            if (y < p[k].v) {
                if (p[k].wh != z) p[k].sec = min(p[k].sec, p[k].v);
                p[k].v = y, p[k].wh = z;
            } else {
                if (p[k].wh != z) p[k].sec = min(p[k].sec, y);
            }
        }
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modify(p[k].l, l, mid, x, y, z);
        } else {
            modify(p[k].r, mid + 1, r, x, y, z);
        }
    }

    int query(int k, int l, int r, int x, int y, int z) {
        if (!k || l > y || r < x) return 1e9;
        if (l >= x && r <= y) {
            return (z == p[k].wh ? p[k].sec : p[k].v);
        }
        int mid = (l + r) >> 1;
        return min(query(p[k].l, l, mid, x, y, z),
                   query(p[k].r, mid + 1, r, x, y, z));
    }

    struct DS6 {
        int rt0, rt1, SZ;

        void Modify(int x, int y, int z, int w) {
            ++x;
            if (!w) modify(rt0, 1, SZ, x, y, z);
            else modify(rt1, 1, SZ, x, y, z);
        }

        int Query(int x, int z, int w) {
            ++x;
            if (!w) return min(query(rt0, 1, SZ, 1, x, z), query(rt1, 1, SZ, 1, x, z));
            return query(rt0, 1, SZ, 1, x, z);
        }
    } seg[N];

    void initDS() {
        for (int i = 1; i <= n; ++i) seg[i].SZ = _SZ[i];
    }
    
    void modify(int x, int y) {
        for (int i = x; i; i = tfa[i]) {
            seg[i].Modify(dis[tdep[i]][x], y, col[tdep[i]][x], anc(x, i));
        }
    }

    int query(int x, int d) {
        int res = 1e9;
        for (int i = x; i; i = tfa[i]) {
            int lim = d - dis[tdep[i]][x];
            if (lim < 0) continue;
            res = min(res, seg[i].Query(lim, col[tdep[i]][x], anc(i, x)));
        }
        return res;
    }
}

namespace DS3 {
    int mn[1 << 20];

    void build(int k, int l, int r) {
        mn[k] = 1e9;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
    }

    void Init() {
        build(1, 1, n);
    }

    void modify(int k, int l, int r, int x, int y) {
        mn[k] = min(mn[k], y);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) modify(k << 1, l, mid, x, y);
        else modify(k << 1 | 1, mid + 1, r, x, y);
    }

    int query(int k, int l, int r, int x, int y) {
        if (l > y || r < x) return 1e9;
        if (l >= x && r <= y) return mn[k];
        int mid = (l + r) >> 1;
        return min(query(k << 1, l, mid, x, y),
                   query(k << 1 | 1, mid + 1, r, x, y));
    }

    int query(int x, int y) {
        int res = 1e9;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) {
                swap(x, y);
            }
            res = min(res, query(1, 1, n, dfn[top[x]], dfn[x]));
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) {
            swap(x, y);
        }
        res = min(res, query(1, 1, n, dfn[x], dfn[y]));
        return res;
    }
}

int M[N], f[N], g[N];

int calc(int x) {
    if (M[x]) return M[x];
    int res = min(DS2::query(x, ob), f[x]);
    res = min(res, DS3::query(x, tFa[x]));
    return M[x] = res;
}

namespace DS4 {
    int mn[1 << 20], lz[1 << 20];

    void build(int k, int l, int r) {
        mn[k] = lz[k] = 1e9;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
    }

    void Init() {
        build(1, 1, n);
    }

    void pushdown(int k) {
        if (lz[k] != 1e9) {
            mn[k << 1] = min(mn[k << 1], lz[k]);
            lz[k << 1] = min(lz[k << 1], lz[k]);
            mn[k << 1 | 1] = min(mn[k << 1 | 1], lz[k]);
            lz[k << 1 | 1] = min(lz[k << 1 | 1], lz[k]);
            lz[k] = 1e9;
        }
    }

    void modify(int k, int l, int r, int x, int y, int v) {
        if (l > y || r < x) return;
        if (l >= x && r <= y) {
            mn[k] = min(mn[k], v);
            lz[k] = min(lz[k], v);
            return;
        }
        pushdown(k);
        int mid = (l + r) >> 1;
        modify(k << 1, l, mid, x, y, v);
        modify(k << 1 | 1, mid + 1, r, x, y, v);
        mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
    }

    void modify(int x, int y, int v) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) {
                swap(x, y);
            }
            modify(1, 1, n, dfn[top[x]], dfn[x], v);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) {
            swap(x, y);
        }
        modify(1, 1, n, dfn[x], dfn[y], v);
    }

    int query(int k, int l, int r, int x) {
        if (l == r) return mn[k];
        pushdown(k);
        int mid = (l + r) >> 1;
        if (x <= mid) return query(k << 1, l, mid, x);
        return query(k << 1 | 1, mid + 1, r, x);
    }
}

pair<int, int> _mn[N], _sec[N];
pair<int, int> _tmx[N], _tsec[N];

signed main() {
    fread(I, 1, 22000038, stdin);
    n = read(), rt = read(), oa = read(), ob = read();
    if (ob >= oa) {
        puts("1");
        return 0;
    }
    for (int i = 1, x, y; i < n; ++i) {
        x = read(), y = read();
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(rt);
    for (int i = 1; i <= n; ++i) {
        if (!Fa[i]) Fa[i] = rt;
        if (!tFa[i]) tFa[i] = rt;
    }
    vector< pair<int, int> > ord;
    for (int i = 1; i <= n; ++i) {
        ord.push_back({dep[i], i});
    }
    sort(ord.rbegin(), ord.rend());
    dfs1(rt), dfs2(top[rt] = rt);
    DS1::Init(), DS4::Init();
    for (int i = 1; i <= n; ++i) {
        DS1::modify(Fa[i], i, i);
        DS4::modify(tFa[i], i, i);
    }
    DS2::Init(), DS3::Init();
    for (int i = 1; i <= n; ++i) {
        _mn[i] = {i, i}, _sec[i] = {1e9, 0};
        for (auto v : G[i]) {
            if (v == fa[i]) continue;
            int val = DS4::query(1, 1, n, dfn[v]);
            if (val < _mn[i].first) _sec[i] = _mn[i], _mn[i] = {val, v};
            else if (val < _sec[i].first) _sec[i] = {val, v};
        }
        _tmx[i] = _tsec[i] = {-1, -1};
    }
    for (auto [t, x] : ord) {
        if (hv[x].empty()) {
            f[x] = DS1::query(1, 1, n, dfn[x]);
        } else {
            for (auto v : hv[x]) {
                f[x] = max(f[x], calc(v));
            }
        }
        DS2::modify(x, f[x]);
        if (x == rt) break;
        if (!~_tmx[fa[x]].first) {
            _tmx[fa[x]] = _tsec[fa[x]] = {0, 0};
            for (auto v : hv[fa[x]]) {
                if (dfn[v] >= dfn[x] && dfn[v] <= dfn[x] + siz[x] - 1 && G[fa[x]].size() - (fa[x] != rt) == 1) {
                    continue;
                }
                int val = calc(v), id = getLst(v, fa[x]);
                if (val > _tmx[fa[x]].first) {
                    if (_tmx[fa[x]].second != id) _tsec[fa[x]] = max(_tsec[fa[x]], _tmx[fa[x]]);
                    _tmx[fa[x]] = {val, id};
                } else {
                    if (_tmx[fa[x]].second != id) _tsec[fa[x]] = max(_tsec[fa[x]], {val, id});
                }
            }
        }
        g[x] = (x == _tmx[fa[x]].second ? _tsec[fa[x]].first : _tmx[fa[x]].first);
        if (!g[x]) {
            g[x] = fa[x];
            if (x == _mn[fa[x]].second) g[x] = min(g[x], _sec[fa[x]].first);
            else g[x] = min(g[x], _mn[fa[x]].first);
        }
        DS3::modify(1, 1, n, dfn[x], g[x]);
    }
    printf("%d\n", f[rt]);
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...