AT_arc098_d Donation 题解

teylnol_evteyl · 2023-06-05 18:55:05 · 题解

一道在 kruskal 重构树上 DP 的题。

首先，捐钱比较难想，可以反过来思考倒着走领钱的思路。

显然，在第一次经过一个节点的时候领钱是最优的，对于节点 i，令 c_i=\max\{a_i-b_i,0\}，若当前的钱数是 v，到节点 i 的条件是 v\ge c_i，如果不满足则把 v 补充到 c_i，同时如果是第一次经过，v 就变成 v+b_i。

对于边 (u_i,v_i)，令边权等于 \max\{c_{u_i},c_{v_i}\} 表示经过这条边当前钱数的最小值，按边权从小到大排序建 kruskal 重构树。

考虑在这棵树上 dp。设 f_u 表示经过所有 u 的子树节点（不一定回到 u）后最小的领到的钱。对于叶子节点，f_u=b_u+c_u；对于非叶子节点，枚举是从哪个子节点来的 u，由于 kruskal 重构树的权值上大下小，只需要考虑这子树到 u 的部分，另一棵子树直接领钱，所有方程为 f_u=\min\{max(f_x,c_u)+s_u-s_x,max(f_y,c_u)+s_u-s_y\}，其中 x,y 分别是 u 的两个儿子，s_u 表示 u 为根的子树内节点 b 值之和。

#include <bits/stdc++.h> 

using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

int n, k, m, a[N], b[N];
struct edge{
    int u, v, w;
    bool operator <(const edge &p) const
    {
        return w < p.w;
    }
}e[N];
int pe[N];
int fa[N], ls[N], rs[N];
LL f[N], s[N];

int gfa(int i)
{
    return i == pe[i] ? i : (pe[i] = gfa(pe[i]));
}

void kruskal()
{
    for(int i = 1; i < n * 2; i ++ ) pe[i] = i;
    k = n;
    sort(e + 1, e + m + 1);
    for(int i = 1; i <= m; i ++ )
    {
        int u = gfa(e[i].u), v = gfa(e[i].v);
        if(u != v)
        {
            fa[u] = fa[v] = pe[u] = pe[v] = ++ k;
            ls[k] = u, rs[k] = v;
            a[k] = e[i].w;
        }
    }
}

void dp()
{
    for(int u = 1; u <= n; u ++ )
    {
        f[u] = a[u] + b[u];
        s[u] = b[u];
    }
    for(int u = n + 1; u <= k; u ++ )
    {
        s[u] = s[ls[u]] + s[rs[u]];
        f[u] = min(max(f[ls[u]], (LL)a[u]) + s[u] - s[ls[u]], max(f[rs[u]], (LL)a[u]) + s[u] - s[rs[u]]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &a[i], &b[i]);
        a[i] = max(a[i] - b[i], 0);
    }
    for(int i = 1; i <= m; i ++ )
    {
        scanf("%d%d", &e[i].u, &e[i].v);
        e[i].w = max(a[e[i].u], a[e[i].v]);
    }
    kruskal();
    dp();
    printf("%lld\n", f[k]);
    return 0;
}