CF860E Arkady and a Nobody-men 题解

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

先考虑编一个暴力 dp。显然可以设

f_u

表示节点

u

的可忽略性，则有转移

f_u = f_{\text{fa}_u} + \text{dep}_{\text{fa}_u} + w_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)

，有转移

\begin{cases} {w_u \leftarrow \text{dep}_{\text{cur}}} \\ {w_v \leftarrow \text{dep}_{\text{cur}}} \end{cases}

一个观察是对于同一层的所有

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

个。转移即为

\begin{cases} {w_p \leftarrow \text{dep}_u \times \text{cnt}_v} \\ {w_v \leftarrow \text{dep}_u \times \text{cnt}_p} \end{cases}

同时让

p

在新树中向

v

即可。二元组可以用任意你喜欢的方式（如链式前向星或指针）维护。该做法的时空复杂度均为

O(n)

。

code

CPP

#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;
}

CF860E Arkady and a Nobody-men 题解

文章操作

相关推荐

评论

CF860E Arkady and a Nobody-men 题解