题解：P10283 [USACO24OPEN] Identity Theft P

· · 题解

怎么只有我是大力做法？

首先在 01-Trie 上考虑，操作就是让一个人往子树里走，需要使得任意两个人不存在祖先后代的关系。

对于点 u 上的人，先保证 u 子树内的其它点都已经合法，那么其余所有人都在叶子上，那么 u 有两种移动方案：

  1. 找到子树内一个度数为 1 的点 v 并成为它的儿子，花费 \text{dep}_v-\text{dep}_u+1；
  2. 找到子树内一个叶节点 v，此时上面一定有人，把这个人和 u 上的那个人移到 v 的左右儿子上面去，花费 \text{dep}_v-\text{dep}_u+2。

容易发现直接贪心地选择花费较少的 v 是正确的，因为留给祖先用并不会使得答案变优，现在问题就在于如何动态维护如上两种点的信息。

把树拍成 dfs 序，使用线段树维护子树内深度最小的一度点和叶节点及其编号，寻找 v 的时候直接在线段树上面区间查即可。

当发生修改时，会插入一些新的节点，直接维护编号是不可行的，但发现新插入的节点形成的子树内一定只有二度点和叶节点，因此对于每个点 u，使用小根堆 Q_u 来维护 u 的新插入的儿子子树中每个可用的叶节点的深度。对于每个叶节点，初始时 Q_u 中仅包含 \text{dep}_u 一个元素；对于非叶节点，初始时 Q_u 为空。

当使用一度点 v 时，将 v 从一度点中移除，并往 Q_v 中插入 \text{dep}_v+1；当使用二度点 v 时，实际上使用的是 Q_v 中深度最小的点，设其深度为 d，则将 d 弹出，再插入两个 d+1。在对 Q 做修改时，同时修改线段树上对应节点的信息。时间复杂度为 \mathcal O(m\log n)。

一个点上可能有很多个人，逐个处理即可。注意叶节点要特判，设有 k 个人，那么只有 k-1 个人需要进行如上步骤。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, INF = 1e9;
int n, m, ch[N][2], deg[N], cnt[N], tot = -1, dfn[N], nfd[N], dep[N], mxd[N], ans;
char s[N]; priority_queue<int, vector<int>, greater<int> > Q[N];
void ins() {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - '0';
        if (!ch[p][c]) ch[p][c] = ++m, deg[p]++;
        p = ch[p][c];
    }
    cnt[p]++;
}
void dfs(int u, int d) {
    nfd[dfn[u] = ++tot] = u, dep[u] = d;
    for (int i : {0, 1}) if (ch[u][i]) dfs(ch[u][i], d + 1);
    mxd[u] = tot;
    if (!deg[u]) Q[u].push(dep[u]);
}
struct node { int p0, d0, p1, d1; } t[N << 2];
node operator+(node a, node b) {
    if (b.d0 < a.d0) a.p0 = b.p0, a.d0 = b.d0;
    if (b.d1 < a.d1) a.p1 = b.p1, a.d1 = b.d1;
    return a;
}
void build(int p, int l, int r) {
    if (l == r) {
        if (!deg[nfd[l]]) t[p].p0 = l, t[p].d0 = dep[nfd[l]];
        else t[p].p0 = -1, t[p].d0 = INF;
        if (deg[nfd[l]] == 1) t[p].p1 = l, t[p].d1 = dep[nfd[l]];
        else t[p].p1 = -1, t[p].d1 = INF;
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    t[p] = t[p << 1] + t[p << 1 | 1];
}
node qry(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return t[p];
    int mid = l + r >> 1;
    if (R <= mid) return qry(p << 1, l, mid, L, R);
    if (L > mid) return qry(p << 1 | 1, mid + 1, r, L, R);
    return qry(p << 1, l, mid, L, R) + qry(p << 1 | 1, mid + 1, r, L, R);
}
void upd1(int p, int l, int r, int x) {
    if (l == r) {
        t[p].p0 = l, t[p].d0 = dep[nfd[l]] + 1;
        t[p].p1 = -1, t[p].d1 = INF;
        Q[nfd[l]].push(dep[nfd[l]] + 1);
        return;
    }
    int mid = l + r >> 1;
    x <= mid ? upd1(p << 1, l, mid, x) : upd1(p << 1 | 1, mid + 1, r, x);
    t[p] = t[p << 1] + t[p << 1 | 1];
}
void upd0(int p, int l, int r, int x) {
    if (l == r) {
        int i = nfd[l], d = Q[i].top(); Q[i].pop();
        Q[i].push(d + 1), Q[i].push(d + 1);
        return t[p].d0 = Q[i].top(), void();
    }
    int mid = l + r >> 1;
    x <= mid ? upd0(p << 1, l, mid, x) : upd0(p << 1 | 1, mid + 1, r, x);
    t[p] = t[p << 1] + t[p << 1 | 1];
}
void Dfs(int u) {
    if (!deg[u]) {
        for (int i = 2; i <= cnt[u]; i++) ans += Q[u].top() - dep[u] + 2, upd0(1, 0, m, dfn[u]);
        return;
    }
    for (int i : {0, 1}) if (ch[u][i]) Dfs(ch[u][i]);
    while (cnt[u]--) {
        node p = qry(1, 0, m, dfn[u], mxd[u]);
        if (p.d1 <= p.d0) ans += p.d1 - dep[u] + 1, upd1(1, 0, m, p.p1);
        else ans += p.d0 - dep[u] + 2, upd0(1, 0, m, p.p0);
    }
}
int main() {
    // freopen("id.in", "r", stdin), freopen("id.out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s, ins();
    dfs(0, 1), build(1, 0, m), Dfs(0);
    cout << ans;
//  while (1);
}