P9128 [USACO23FEB] Fertilizing Pastures G

· · 题解

先考虑 T=0 时怎么做。显然，最优的遍历顺序是树的某个 DFS 序，对于 n 个点的树遍历的步数是 2n-2。我们只需要对于每个节点 u，决定其儿子的遍历顺序。

设 f_u 为 u 子树内的答案，sz_u 为 u 子树的大小，sum_u 为 u 子树内 a_i 的和。假设我们现在在 u，先进入了别的子树，经过 T 时间后再进入 v，我们把每个节点的贡献拆开，可以得到 v 对 f_u 的贡献是 sum_v \times T + f_v。而当我们确定顺序后，遍历某个子树 v 之前的子树所需的时间是确定的，相当于有 k 个二元组 (a_i,b_i)，其中 a_i = sum_{v_i},b_i = 2 \times sz_{v_i}，求一个排列 p 使得 \sum \limits_{i = 1}^k \left( a_{p_i} \times \big( \sum \limits_{j=1}^{j<i} b_{p_j} + 1 \big) + f_{p_i} \right) 最小。

式子中和 f 有关的项都是确定的，我们要最小化的其实是 \sum \limits_{i = 1}^k a_{p_i} \times \sum \limits_{j=1}^{j<i} b_{p_j}。这是个经典 exchange argument，考虑序列中相邻的两个位置 i,i+1，显然交换他们不会影响其他项的贡献。设 i 之前的 b_i 和为 S，如果交换后答案变得更优，那么有 a_i \times S + a_{i+1} \times (S + b_i) > a_{i+1} \times S + a_{i} \times (S + b_{i+1})，即 \frac{a_{i+1}}{b_{i+1}} > \frac{a_i}{b_i}。这个条件也是充要的，也就是说，如果序列中存在相邻两个位置满足这个条件，那么交换后答案一定更优。

那么最优的顺序一定按照 \frac{a_i}{b_i} 降序排列，据此容易计算答案，总时间复杂度 \mathcal{O}(n \log n)。

对于 T = 1 有相似的结论，如果我们停留在深度为 d 的节点，那么遍历的最小步数为 (2n - 2) - d。所以我们最后一定会停留在深度最大的节点。

设最大深度为 D。同样，我们还是需要为每个节点决定其儿子的遍历顺序，但与之前不同的是，我们需要选择一个儿子 v 满足其子树内存在深度为 D 的节点，把 v 留到最后进入。我们可以先预处理出哪些节点可以作为这样的 v，而对于剩余的儿子节点，和 T=1 时一样，按照 \frac{a_i}{b_i} 排序即可。

当然，我们不可能对于每个可能的 v 都排一遍序。一个简单的优化方式是，由于每次确定 v 后其余的节点都是按照 \frac{a_i}{b_i} 排序，因此这和 T=0 时的结果只会有一项不同，我们可以先算出 T=0 时的答案，枚举 v 时扣掉 v 的贡献，然后加上把 v 放在最后的贡献。这可以通过一些简单的预处理做到单次 \mathcal{O}(1)。总时间复杂度 \mathcal{O}(n \log n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
const LL inf = 2e18;
int n, t, mxd, a[N], sz[N], dep[N]; LL sum[N], f[N], g[N], suf[N];
bool mark[N];
vector <int> e[N];
struct dat {
    LL a, b; int v;
} d[N];
void dfs0(int u) {
    for (auto v : e[u]) dfs0(v), dep[u] = max(dep[u], dep[v] + 1);
}
void ptag(int u, int d) {
    if (d + dep[u] == mxd) mark[u] = 1;
    for (auto v : e[u]) ptag(v, d + 1);
}
void dfs(int u) {
    sz[u] = 1, sum[u] = a[u];
    int m = 0;
    for (auto v : e[u]) {
        dfs(v);
        sz[u] += sz[v], sum[u] += sum[v];
        f[u] += f[v];
    }
    for (auto v : e[u]) {
        d[++m] = (dat){ sum[v], 2 * sz[v], v };
    }
    sort(d + 1, d + m + 1, [&](dat i, dat j) { return j.a * i.b < i.a * j.b; });
    LL val = 0, sb = 1;
    for (int i = 1; i <= m; i++) {
        val += d[i].a * sb, sb += d[i].b;
    }
    suf[m + 1] = 0;
    for (int i = m; i >= 1; i--) suf[i] = suf[i + 1] + d[i].a;
    LL ret = inf, pre = 1;
    for (int i = 1; i <= m; i++) {
        int v = d[i].v;
        if (mark[v]) ret = min(ret, f[u] - f[v] + g[v] + val - d[i].b * suf[i + 1] - d[i].a * pre + d[i].a * (sb - d[i].b));    
        pre += d[i].b;  
    }
    f[u] += val, g[u] = ret;
    if (m == 0) g[u] = 0;
}
int main() { 
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> t;
    for (int i = 2, ff; i <= n; i++) {
        cin >> ff >> a[i];
        e[ff].push_back(i);
    }
    dfs0(1), mxd = 0;
    for (int i = 1; i <= n; i++) mxd = max(mxd, dep[i]);
    ptag(1, 0), dfs(1);
    if (t == 0) cout << 2 * (n - 1) << " " << f[1] << "\n";
    else cout << 2 * (n - 1) - mxd << " " << g[1] << "\n";
    return 0;
}