[CF1363E] Tree Shuffling

Description

给定一棵树，每个点有一个代价 (a_i)，一个初始值 (b_i) 和一个目标值 (c_i)，每次可以选择以 (u) 为根的子树，选择一个 (k) 并选择子树中 (k) 个结点交换其值，代价 (k cdot a_u)。求最小代价。

Solution

树上前缀 (min) 后，显然对于任意两个需要交换的点我们用且只会用它的 LCA 处来作为交换操作的根。

因此我们只需要把整棵树 DFS 一遍，在每个点处贪心交换所有能交换的，剩余的上传即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n, a[N], b[N], c[N];
vector<int> g[N];

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i] >> c[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    function<void(int, int)> dfs1 = [&](int p, int fa) -> void {
        for (int q : g[p])
        {
            if (q != fa)
            {
                a[q] = min(a[q], a[p]);
                dfs1(q, p);
            }
        }
    };

    dfs1(1, 0);

    int ans = 0;

    function<pair<int, int>(int, int)> dfs2 = [&](int p, int fa) -> pair<int, int> {
        pair<int, int> res = {b[p] > c[p], b[p] < c[p]};
        for (int q : g[p])
        {
            if (q != fa)
            {
                auto tmp = dfs2(q, p);
                res.first += tmp.first;
                res.second += tmp.second;
            }
        }
        int mn = min(res.first, res.second);
        res.first -= mn;
        res.second -= mn;
        ans += mn * a[p];
        return res;
    };

    auto tmp = dfs2(1, 0);

    if (tmp.first || tmp.second)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans*2<< endl;
    }
}