题解：P9128 [USACO23FEB] Fertilizing Pastures G

· · 题解

\Large{\text{Solution}}

::::warning[要仔细读题！！！]{open} 首先要注意 先满足时间最短，再满足花费最小。差点止步于此。 ::::

::::info[本题解中变量的含义]{open} 题解中变量和代码中相同。

那么显然当 T=0 时时间最短是走每条边两次，即用时 2n-2。T=1 时显然是少走一条离根节点最远的路，所以用时为 n-maxd。

那么现在看花费的问题。先看 T=0，对于每一个子树的根节点 u，我们要决定遍历它儿子的顺序。因为要回到起点，所以可以随意调换顺序。

这个时候我们注意到，调换原本顺序相邻的两个对其他子树的贡献没有影响，因为遍历他们的时刻是相同的，所以这个时候就变成了一个经典的 邻项交换 贪心问题。算一下两者贡献就会发现：当两个相邻的根为 i,j 的子树满足 sum_jsiz_i>sum_isiz_j 就应该交换 i,j。

此时，我们再按序遍历，树形 DP。记录每个节点的 f。输出 f_1 即可。

再看 T=1。不难发现我们按照刚刚的逻辑只需要把一个可能为终点的子树（即子树中有点的深度为 maxd）放到遍历顺序的最后。那么所有在 i 之后的点都要减去遍历 i 子树时间的贡献，同时减去 i 子树的所有贡献，把 g_i 的贡献添上。

这里没有直接给出 f_i,g_i 的推导过程和一些细节的实现，希望读者自行思考后再看我的一坨代码。

::::success[代码]

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 2e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
//const int mod = 998244353;

int a[N], d[N], sum[N], siz[N], maxd;
int presum[N], presiz[N], f[N], g[N];
vector <int> v[N];
bool vis[N];
void dfs_d(int u)
{
    maxd = max (maxd, d[u]), sum[u] = a[u], siz[u] = 1;
    for (int j : v[u])
    {
        d[j] = d[u] + 1, dfs_d (j);
        sum[u] += sum[j], siz[u] += siz[j];
    }
}
void dfs_vis(int u)
{
    if (d[u] == maxd) vis[u] = true;
    for (int j : v[u])
        dfs_vis (j), vis[u] |= vis[j];
}
bool cmp(int x, int y) {return sum[x] * siz[y] > sum[y] * siz[x];}
void dfs(int u)
{
    // cout << u << " " << a[u] * t << "\n";
    sort (v[u].begin (), v[u].end (), cmp);
    int t = 0;
    for (int i = 0; i < v[u].size (); i++)
    {
        int j = v[u][i];
        // cout << j << "--" << t + 1 << "\n";
        if (i) presum[j] = presum[v[u][i - 1]] + sum[v[u][i - 1]], presiz[j] = presiz[v[u][i - 1]] + siz[v[u][i - 1]];
        dfs (j);
        f[u] += f[j] + (t + 1) * sum[j], t += 2 * siz[j];
    }
    // cout << u << " " << f[u] << "\n";
}
void dfs2(int u)
{
    g[u] = 9e18;
    int t = 0;
    for (int i = 0; i < v[u].size (); i++)
    {
        int j = v[u][i];
        if (!vis[j]) continue;
        dfs2 (j);
        t = 2 * presiz[j];
        int val = f[u] - f[j] - (t + 1) * sum[j] - (sum[u] - a[u] - presum[j] - sum[j]) * 2 * siz[j] + g[j] + (2 * (siz[u] - 1 - siz[j]) + 1) * sum[j];
        g[u] = min (g[u], val);
    }
    if (g[u] == 9e18) g[u] = 0;
    // cout << u << " " << t << " " << g[u] << "\n";
}

signed main()
{
    int n, T;
    cin >> n >> T;
    for (int i = 2; i <= n; i++)
    {
        int x;
        cin >> x >> a[i];
        v[x].push_back (i);
    }
    dfs_d (1), dfs_vis (1);
    dfs (1);
    if (T == 0) return cout << 2 * (n - 1) << " " << f[1] << "\n", 0;

    // for (int i = 1; i <= n; i++) cout << vis[i] << " "; puts ("");

    dfs2 (1);
    cout << 2 * (n - 1) - maxd << " " << g[1] << "\n";
    return 0;
}

::::