题解：P17851 「RiOI-(-2)」houran 和芒果 / [ROI 2026 Day1] 泰莫利亚的调查 加强版

· · 题解

保证开到了 std 的 1.5 倍。

直接 dp。设 dp_{u,i} 表示 u 子树内选了 i 条链的最大值。对 u 的儿子 v 逐个合并时，我们按照 u\to v 的边权 w 从大到小合并。有两种转移：

也就是说，当 dp_u 要合并上 dp_v 时，会做这样两个转移：

凸性并不显然，棘手的主要是第二个转移比较难以想象，不过可以发现：如果假设 dp_{u,0}=w，那么这一步可以和第一个转移合并。于是我们可以这样：

由于合并过程中 w 是单调不增的，因此任何时刻 dp 也是凸的。用任意可并堆维护即可做到 \mathcal{O}(n\log n)。

:::info[这部分的代码实现]

#include <bits/stdc++.h>

using namespace std;

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)

inline 
int read() {
    int x = 0; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar());
    for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = getchar());
    return x;
}

typedef long long ll;

const int MAXN = 2e5 + 10;

struct node { int l, r; ll x; } t[MAXN]; int rt[MAXN], tot;

int merge(int u, int v) {
    if (!u || !v) return u | v;
    if (t[u].x < t[v].x) swap(u, v);
    t[u].r = merge(t[u].r, v), swap(t[u].l, t[u].r);
    return u;
}

vector<pair<int, int>> g[MAXN];

void dfs(int u, int f = 0) {
    sort(g[u].begin(), g[u].end(),
        [](const auto &x, const auto &y) { return x.second > y.second; });
    for (auto _ : g[u]) {
        int v = _.first, w = _.second;
        if (v == f) continue; dfs(v, u);
        if (rt[u]) t[rt[u]].x -= w;
        rt[u] = merge(rt[u], rt[v]);
        if (rt[u]) t[rt[u]].x += w;
    }
    if (!rt[u]) rt[u] = ++tot;
}

int T, n, m, f[MAXN], w[MAXN], x[4]; ll sum;

int main() {
    n = read(); 
    for (int i = 2; i <= n; i++) f[i] = read();
    for (int i = 2; i <= n; i++) w[i] = read();
    for (T = read(); T--; ) {
        x[0] = read(), x[1] = read(), x[2] = read(), x[3] = read(), m = read();
        for (int i = 2; i <= n; i++) w[i] ^= x[i & 3];
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i <= n; i++) rt[i] = 0; sum = 0;
        for (int i = 1; i <= tot; i++) t[i].l = t[i].r = t[i].x = 0; tot = 0; 
        for (int i = 2; i <= n; i++) g[f[i]].emplace_back(i, w[i]); dfs(1);
        for (int u = rt[1]; m--; ) sum += t[u].x, u = merge(t[u].l, t[u].r);
        for (int i = 2; i <= n; i++) w[i] ^= x[i & 3];
        printf("%lld\n", sum);
    }
}

:::

重温一下 dp 式子后，可以发现：我们竟然从始至终都只关心最大的斜率！其他斜率只是朴素地参与排序罢了。于是，我们甚至只需要记录每个位置的斜率最大值，其它斜率扔进一个数组排序即可。这样就做到排序外线性。

:::info[这部分的代码实现]

#include <bits/stdc++.h>

using namespace std;

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)

inline 
int read() {
    int x = 0; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar());
    for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = getchar());
    return x;
}

typedef long long ll;

const int MAXN = 2e5 + 10;

vector<pair<int, int>> g[MAXN];

ll dp[MAXN], t[MAXN]; int tp; 

void dfs(int u) {
    sort(g[u].begin(), g[u].end(),
        [](const auto &x, const auto &y) { return x.second > y.second; });
    for (auto _ : g[u]) {
        int v = _.first, w = _.second; dfs(v);
        if (!dp[u]) { dp[u] = dp[v] + w; continue; }
        if ((dp[u] -= w) < dp[v]) swap(dp[u], dp[v]);
        dp[u] += w, t[tp++] = dp[v];
    }
}

int T, n, m, f[MAXN], w[MAXN], x[4]; ll sum;

int main() {
    n = read(); 
    for (int i = 2; i <= n; i++) f[i] = read();
    for (int i = 2; i <= n; i++) w[i] = read();
    for (T = read(); T--; ) {
        x[0] = read(), x[1] = read(), x[2] = read(), x[3] = read(), m = read();
        for (int i = 2; i <= n; i++) w[i] ^= x[i & 3];
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i <= n; i++) dp[i] = t[i] = 0; tp = 0;
        for (int i = 2; i <= n; i++) g[f[i]].emplace_back(i, w[i]);
        for (int i = 2; i <= n; i++) w[i] ^= x[i & 3];
        dfs(1), t[tp++] = dp[1], sort(t, t + tp, greater<ll>()), sum = 0;
        for (int i = 0; i < m && i < tp; i++) sum += t[i];
        printf("%lld\n", sum);
    }
}

:::

考虑干掉排序。对于边的排序，我们只需要给每个点的出边进行排序，可以先对所有边排序，再加到树中，因此在外层做计数排序即可。对于斜率实际上只要求全局前 m 大，使用 nth_element 即可做到 \mathcal{O}(n)。于是本题在线性的时间复杂度内解决。