CF860E Arkady and a Nobody-men 题解

zyb_txdy · 2025-11-17 21:30:07 · 题解

感觉很牛啊，算是一道并不模板的长剖优化 dp 好题了。

先考虑编一个暴力 dp。显然可以设 f_u 表示节点 u 的可忽略性，则有转移

其中 w_u 表示与 u 的深度相同的点对 u 的贡献和。

现在考虑怎么求 w_u。最暴力的方法是你对于每个节点 u 都记录一些三元组 (v, \text{dep}_v, w_v)，其中的变量分别表示 u 的子树内存在的一个节点、其深度与已经计算的同层贡献。直接计算是 O(n^2) 的。

考虑如何优化。我们把转移 w 的过程（即对于当前考虑的节点，合并其两棵子树的三元组的过程）写下来，即对于当前节点 \text{cur}，枚举分别在已经处理过的子树与当前考虑的子树中的同深度三元组 (u, \text{dep}_u, w_u) 与 (v, \text{dep}_v, w_v)，有转移

一个观察是对于同一层的所有 u，当前子树对它们的贡献是相同的（设同层的 v 的数量为 \text{cnt}，则贡献为 \text{dep}_{\text{cur}} \times \text{cnt}），对 v 同理。因此考虑对于每个深度只保留一个点，并建立一棵新树表示贡献的传递关系。树中的边 u \xrightarrow{\text{val}} v 表示 w_v = w_u + \text{val} 恒成立。此时合并子树的代价就变成了 O(树高)，长剖优化即可。

具体地，对于节点 u 及其子树内存在的深度 d，记录二元组 (p, \text{cnt}_p)，表示 子树中深度为 d 的点由 d 代表，同时这样的点实际有 \text{cnt}_p 个。转移即为

同时让 p 在新树中向 v 即可。二元组可以用任意你喜欢的方式（如链式前向星或指针）维护。该做法的时空复杂度均为 O(n)。

::::info[code]

#include <bits/stdc++.h>
#define ll long long

using namespace std;

constexpr int N = 5e5 + 5;

int n, rt;
int fa[N], dep[N], h[N], son[N];
ll ans[N];
vector<int> e[N];
vector<array<ll, 2>> E[N];
int buf1[N], *p1 = buf1, *p[N];
int buf2[N], *p2 = buf2, *cnt[N];

void dfs1(int u) {
    h[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    for (auto v : e[u]) {
    dfs1(v);
        h[u] = max(h[u], h[v] + 1);
        if (h[v] > h[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp) {
    if (u == tp) {
        p[u] = p1;
        p1 += h[u];
        cnt[u] = p2;
        p2 += h[u];
    }
    if (son[u]) {
        p[son[u]] = p[u] + 1;
        cnt[son[u]] = cnt[u] + 1;
        dfs2(son[u], tp);
    }
    p[u][0] = u, cnt[u][0] = 1;
    for (auto v : e[u]) {
        if (v == son[u]) continue;
        dfs2(v, v);
        for (int i = 0; i < h[v]; ++i) {
            ans[p[u][i + 1]] += 1ll * dep[u] * cnt[v][i];
            ans[p[v][i]] += 1ll * dep[u] * cnt[u][i + 1];
            E[p[u][i + 1]].push_back({p[v][i], ans[p[v][i]] - ans[p[u][i + 1]]});
            cnt[u][i + 1] += cnt[v][i];
        }
    }
}

void dfs3(int u, bool flag) {
    if (flag && son[u]) {
        dfs3(son[u], flag);
    }
    for (auto cur : E[u]) {
        ans[cur[0]] = ans[u] + cur[1];
        dfs3(cur[0], false);
    }
}

void dfs4(int u) {
    for (auto v : e[u]) {
        ans[v] += ans[u] + dep[u];
        dfs4(v);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> fa[i];
        if (fa[i] > 0) {
            e[fa[i]].push_back(i);
        } else {
            rt = i;
        }
    }

    dfs1(rt);
    dfs2(rt, rt);
    dfs3(rt, true);
    dfs4(rt);

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " \n"[i == n];
    }

    return 0;
}

::::