[Bzoj 3252] 攻略 题解

攻略

题面

\(n(\le2\cdot10^5)\) 个点的有根树，\(k(\le n)\) 次从根走到叶子，每个点有权值，求经过的点的权值和的最大值.（同一个点只能算一次）

Sol 1

我们设想一个叶子一个叶子加进去的过程。

如果有两个从某个点到叶子的路径，我们可以如图把他分成两条路径。

那么他满足贪心，也就是每次选能产生最大贡献的叶子加入，最后的答案是最优的。

因为如果一个最优的叶子当前没有被加入，那你后面始终可以通过加入这个叶子得到更好的答案。

另外这个贪心感性理解上也是比较显然的。

由于同一个经过的点的权值不能被算多次，我们每加入一条从叶子一直往上的路径，就把路径上的点全部删除。

注意删除这条路径还会给剩下的叶子的贡献造成影响。

那么我们维护这个贪心就行了：

1. 找到最优的点
2. 沿这个点往上爬，一边爬一边删除这个点，同时修改这个点的子树中的叶子的贡献

我们发现这个东西很多数据结构都可以维护，这里我们使用线段树：

1. 找最优的点，也就是找贡献最大的点，相当于求全局最大值、最大值的编号
2. 修改子树中所有叶子的贡献，也就是将子树中所有叶子的贡献减去这个点本身的权值，相当于区间减

总体来说，最多删 \(n\) 个点，每次删点区间修改 \(\mathcal O(\log n)\)，\(k\) 次全局查询，直接 \(\mathcal O(1)\) 返回线段树根节点的数据即可，总复杂度 \(\mathcal O(n\log n)\).

上面已经讲的很清楚了，同时不建议看代码

#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
typedef long long ll;
constexpr int N = 2e5 + 10;
int n, k, m, fa[N], in[N], out[N], rev[N];
ll ans, a[N], b[N], c[N];
vector<int> G[N];
void dfs(int u) { b[u] += b[fa[u]]; if (G[u].empty()) return in[u] = out[u] = ++m, rev[m] = u, c[m] = b[u], void(); in[u] = m + 1; for (int v : G[u]) dfs(v); out[u] = m; }
// 预处理: 每个子树包含的叶子节点区间、每个叶子的贡献
struct Seg {
    ll mx[N << 2], add[N << 2]; int mxid[N << 2];
#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)
    inline void push_up(int u) { mx[u] = max(mx[lc], mx[rc]), mxid[u] = mx[lc] > mx[rc] ? mxid[lc] : mxid[rc]; }
    inline void push_down(int u) { if (add[u]) mx[lc] += add[u], mx[rc] += add[u], add[lc] += add[u], add[rc] += add[u], add[u] = 0; }
    void build(int u, int l, int r) { add[u] = 0; if (l == r) return mx[u] = c[l], mxid[u] = l, void(); build(lc, l, mid), build(rc, mid + 1, r), push_up(u); }
    void upd(int u, int l, int r, int x, int y, ll v) { if (x <= l && r <= y) return mx[u] += v, add[u] += v, void(); push_down(u); if (x <= mid) upd(lc, l, mid, x, y, v); if (mid < y) upd(rc, mid + 1, r, x, y, v); push_up(u); }
} t;
// 区间加、全局查最大值及编号的线段树
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i]; for (int i = 1, u, v; i < n; i++) cin >> u >> v, G[u].pb(v), fa[v] = u;
    dfs(1); t.build(1, 1, m); while (k--) { ans += t.mx[1]; int u = rev[t.mxid[1]]; while (u) { for (int v : G[u]) fa[v] = 0; t.upd(1, 1, m, in[u], out[u], -a[u]), G[u].clear(), u = fa[u]; } }
    // k 次贪心
    cout << ans << "\n";
    return 0;
}

Sol 2

我们继承 Sol 1 的分路径思想和贪心思想。

我们发现贪心选择路径的顺序是固定的，同时如果更深一步思考，会发现这些叶子往上分得的路径从始至终都是固定的。

尝试预处理出这些路径，那么我们从大到小依次选出所含权值和最大的 \(k\) 个路径即可。

我们这样分配路径：

我们像树链剖分一样，让一条从父节点延伸下来的路径往当前节点的一个儿子延伸，使这条路径上的点权之和最大；其余的儿子新开一条路径，成为这条路径的起始点。称这个儿子为当前节点的重儿子。

那么每个叶子节点恰好被一条路径包含；所有路径一共不重不漏恰好包含所有节点；包含根节点的路径的点权之和是最优的。

同时仔细想想就知道 Sol 1 中的一开始就固定的路径分配集合恰好就是我们分配出来的这样。

然后对每条路径的权值和排序，从大到小选 \(k\) 个加入答案即可。

预处理是 \(\mathcal O(n)\) 的，总复杂度 \(\mathcal O(n\log n)\)，瓶颈在于排序。

代码针对可读性做了优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 2e5 + 10;
int n, k, tot, a[N], son[N];
ll ans, len[N], s[N];
vector<int> G[N];
void dfs(int u, int f) {
    for (int v : G[u]) dfs(v, u), son[u] = len[v] > len[son[u]] ? v : son[u];
    len[u] = len[son[u]] + a[u];
    for (int v : G[u])
        if (v != son[u]) s[tot++] = -len[v];
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    dfs(1, 0); ans = len[1];
    sort(s, s + tot);
    for (int i = 0; i < min(k - 1, tot); ++i) ans -= s[i];
    printf("%lld\n", ans);
    return 0;
}

Sol 3

有一个显然的树形 dp：

\(f_{u,i}\) 表示 \(u\) 子树走到叶子 \(i\) 次的权值和最大值.

\(f_{u,i}=\max f_{u,j}+f_{v,i-j},j\in[0,\min(son(u),i)]\)

其中 \(v\) 为 \(u\) 儿子，\(son(u)\) 表示 \(u\) 子树内的叶子节点个数。

因为叶子节点个数不超过子树大小，\(k\) 与 \(n\) 同阶，所以复杂度比 \(\mathcal O(n^2)\) 小，但是最大是 \(\mathcal O(n^2)\)，比如菊花图。

发现这是 \((+,\max)\) 形式的卷积，同时 \(f_{u,i}\) 随 \(i\) 单调递增，可以闵可夫斯基和优化。

然后就没了。

代码还没写。