Fertilizing Pastures (USACO Gold 2023 February)

观察题意，首先注意到要的是最短完成时间，然后在最短时间基础上再要求最小代价。所以比较容易看出来，我们不能浪费时间，进入一个子树后必须全部走完才能出来。然后才是在这个时间下的最低代价。

子任务1: T=0。

这时候遍历完所有节点再回到根，所需最短时间是一个固定值，就是 $2(N-1)$ 。然后要求最小代价。在树上求代价和价值这些题，当然比较常见做法是Tree DP，就是以子树为单位进行计算。这里我们尝试把代价本地化到子树，如果我们假设从0时间开始的子树 $u$ 的贡献是 $\text{dp}[u]$ ，则从 $t$ 时间到达 $u$ 的情况下，子树 $u$ 的总贡献是： $\text{dp}[u] + tA[u]$ , $A[u]$ 是u子树的 $a[]$ 之和。

从例子数据可以看出来，以不同顺序访问子树的时候，总的代价是不同的（就是上面公式里 $tA[u]$ 的部分）。我们看怎样找到最优顺序，首先全部生成所有顺序，或者bitmask DP之类都是不现实的，因为孩子可能非常多。所以猜测存在贪心之类的办法，基于邻项交换法，在一个固定的子树访问顺序中，如果相邻的 $i,j$ 交换顺序，结果都变差，那么这个顺序就是最优的。所以我们只需要考虑相邻两个怎样选择顺序：

$i$ 在 $j$ 前面： $\text{dp}[i] + \text{dp}[j] + S[i] \cdot A[j]$ , $j$ 在 $i$ 前面： $\text{dp}[i] + \text{dp}[j] + S[j] \cdot A[i]$ , 其中 $S[i]$ 是 $i$ 子树的大小。

所以可以推出， $S[i]/A[i]$ 越小的，应该就越放在前面。这样就找到了一个最优的贪心的顺序。从另一个角度来看，这是可以看成是最短任务优先调度策略的一个推广情况， $2S[i]$ 是子树需要的时候，当 $A[i]=1$ 时，就退化了最短任务优先。

最后结果是 $\text{dp}[0]$ 。

具体实现中有一个要注意：树的深度很大，DFS会stack overflow而不能使用，所以需要用for loop来遍历。从最后一个节点倒着往前走，这是个常见的遍历方法。

子任务2: T=1。

此时不要求最后回到根，显然要想让时间最短，我们需要最后停在树的最深处，时间减掉最大深度。同时要使最后停在最深处，从根出发时，需要保证有一个最深的子树在访问次序最后，进入这个子树要重复这个动作。我们通过新增一个 $\text{dp2}[i]$ ，来维护如果 $i$ 子树需要将一个最深子树放在最后情况下的最优结果。

$\text{dp2}[i]$ 的计算方法如下：在每个节点 $i$ 处，枚举所有最深的子树，将这个子树 $u$ 放到最后。则和原来的最优顺序相比，我们新增了一些代价，又减少了一些代价：

$u$ 自己的代价新增了: $2A[u]\sum_v S[v]$ , $v$ 是原顺序中 $u$ 之后的所有子树。
所有 $u$ 之后的 $v$ 都向前移动，代价减少了： $2S[u]\sum_v A[v]$ 。
因为最后不需要回到根节点，代价减少了： $\text{dp}[u]-\text{dp2}[u]$ 。

通过这个办法，就可以基于计算出 $\text{dp2}[u]$ 。最后结果就是 $dp2[0]$ 。公式里的两个求和都可以滚动进行（是两个suffux sum）。最后复杂度是 $\mathcal{O}(N)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, T;
int a[200005];
vector<int> g[200005];      // children of each node
ll A[200005], S[200005];    // total weight and size of subtree
ll dp[200005];              // dp[i]: total cost starting from subtree i at time 0
ll dp2[200005];
int depth[200005];
 
int main() {
    scanf("%d %d", &n, &T);
    for (int i = 1; i < n; i++) {
        int p;
        scanf("%d %d", &p, &a[i]);
        p--;
        g[p].push_back(i);
    }
    for (int i = n-1; i >= 0; i--) {
        for (int u: g[i]) {
            A[i] += A[u];
            S[i] += S[u];
            depth[i] = max(depth[i], depth[u]+1);
        }
        S[i]++;
        A[i]+=a[i];
    }
    for (int i = n-1; i >= 0; i--) {
        sort(g[i].begin(), g[i].end(), [](int a, int b) -> bool { // S[a]/A[a] < S[b]/A[b] 
            return S[a]*A[b] < S[b]*A[a];
        });
        ll tot = A[i] - a[i];
        for (int u: g[i]) {
            tot -= A[u];
            dp[i] += tot * 2 * S[u] + dp[u] + A[u];
        }
        if (T && g[i].size()) {
            ll Asum = 0, Ssum = 0;      // suffix sum of A and S
            dp2[i] = INT64_MAX;
            for (int j = g[i].size()-1; j >= 0; j--) {  // decreasing order
                int u = g[i][j];
                if (depth[u] + 1 == depth[i])
                    dp2[i] = min(dp2[i], dp[i] - Asum*2*S[u] + A[u]*2*Ssum - dp[u] + dp2[u]);
                Asum += A[u]; Ssum += S[u];
            }
        }
    }
    if (T)
        printf("%d %lld\n", 2*(n-1)-depth[0], dp2[0]);
    else printf("%d %lld\n", 2*(n-1), dp[0]);
    return 0;
}