P11038 题解

· · 题解

鲜花：这题 idea 来自我真名的拼音首字母缩写。

首先考虑一个 O(n^2) 的 dp。先枚举 i，然后设 dp_u 为 u 子树内的答案。对于 u 的儿子 v，若定为重儿子则造成 dp_v 的贡献，否则造成 dp_v+w_{u,v} 的贡献。最优策略就是贪心地将 dp_v+w_{u,v} 的前 i 大设为重儿子，可以得到转移：

dp_u=\max((i+1)_{\text{th}}(\{dp_v+w_{u,v}\mid v\in\operatorname{son}(u)\}),\max_{v\in\operatorname{son}(u)}dp_v)

其中 k_{\text{th}}(S) 表示集合 S 内的第 k 大。单次可用 nth_element 函数做到 O(n)。

可以发现一个事情：当 i\ge d_u 时，我们可以把它的所有儿子都设为重儿子。所以这些 u 本质上是没用的，只要保留所有 d_u>i 的节点后建虚树，节点总数是 O(\sum^{n-1}_i\sum_u[d_u>i])=O(\sum_ud_u)=O(n) 的。

但是转移复杂度还是错的啊？你先别急，我们每个节点开一个平衡树/可删对顶堆，维护其下所有 dp_v+w_{v,u} 的值即可。新建虚树时暴力删除所有删掉的节点，进行 dp 时暴力加上所有有用的节点，修改次数是 O(n) 的。

但是虚树是 10 级算法我不会啊？你先别急，我们可以在 i=x-1 的虚树上面建 i=x 的虚树，每次搜第一遍找出哪些点要用，再搜第二遍连父亲即可，时间复杂度是所有虚树的大小总和，也是 O(n) 的。总复杂度带个 priority_queue 或者 multiset 的 log。

代码异常简单。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;

struct heap {

    multiset<ll, greater<ll>> s1, s2;

    void insert(ll x) {
        if (s2.empty() || x >= *s2.begin()) s1.insert(x);
        else s2.insert(x);
    }

    void erase(ll x) {
        if (s1.find(x) != s1.end()) s1.erase(s1.find(x));
        else if (s2.find(x) != s2.end()) s2.erase(s2.find(x));
    }

    ll kth(int rk) {
        if (rk > s1.size() + s2.size()) return 0;
        for (; s1.size() < rk; s1.insert(*s2.begin()), s2.erase(s2.begin()));
        for (; s1.size() > rk; s2.insert(*--s1.end()), s1.erase(--s1.end()));
        return s2.empty() ? 0 : *s2.begin();
    }

} s[MAXN]; 

struct node {
    int v, w;
    node(int v = 0, int w = 0) : v(v), w(w) {}
}; vector<node> g[MAXN], tg[MAXN];

int k, d[MAXN]; ll dp[MAXN];

void dfs(int u, int f) {
    ll res = 0;
    for (node p : g[u]) {
        if (p.v == f) continue; dfs(p.v, u);
        res = max(res, dp[p.v]), s[u].insert(dp[p.v] + p.w);
    }
    dp[u] = max(res, s[u].kth(k));
}

int vis[MAXN], sz[MAXN];

void init(int u, int f) {
    int cnt = 0; sz[u] = vis[u] = (!f || d[u] > k);
    for (node p : g[u]) {
        if (p.v == f) continue; init(p.v, u);
        if (sz[p.v]) cnt++; sz[u] += sz[p.v];
    }
    if (!vis[u] && cnt > 1) vis[u] = 1, sz[u]++;
}

void build(int u, int f, int t, int w) {
    for (node p : g[u]) if (p.v != f) s[u].erase(dp[p.v] + p.w);
    for (node p : g[u]) if (p.v != f && !sz[p.v]) s[u].insert(p.w);
    if (vis[u]) { if (t) tg[t].emplace_back(u, w); t = u; }
    else for (node &p : g[u]) p.w = w;
    for (node p : g[u]) if (p.v != f && sz[p.v]) build(p.v, u, t, p.w);
    g[u] = tg[u], tg[u].clear();
}

int n;

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v, w; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        g[u].emplace_back(v, w), d[u]++;
        g[v].emplace_back(u, w), d[v]++;
    }
    for (int i = 2; i <= n; i++) d[i]--;
    dfs(1, 0), printf("%lld ", dp[1]);
    for (k = 1; k < n; k++) {
        init(1, 0), build(1, 0, 0, 0), dfs(1, 0);
        printf("%lld ", dp[1]);
    }
}

审核说还存在一个长剖做法，但是我不会长剖，有会的同学可以写一下谢谢喵。

赛时被骂说这题跟 TECHNOPOLIS 2085 太卡常了，一看写的不是直接搜而是 10 级算法，令人忍俊不禁。