Codeforces Round 646 (Div. 2) E. Tree Shuffling（树，贪心）

题目链接

Codeforces Round 646 (Div. 2) E. Tree Shuffling

思路

考虑一个节点$u$，显然它子树中的操作可以由它本身和祖先来进行。如果它的祖先有比它花费更小的，直接跳过节点$u$。

我们分别记录每一个子树中位置不对的$0$和$1$的个数，每次操作选出较小的那一个即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, ans;
int a[N], b[N], c[N], cnt[N][2], dp[N];
vector<int>mp[N];
void dfs(int u, int fu)
{if (b[u] != c[u])cnt[u][b[u]]++;for (int j : mp[u]){if (j == fu) continue;dfs(j, u);cnt[u][0] += cnt[j][0], cnt[u][1] += cnt[j][1];}
}
void dfs1(int u, int fu)
{dp[u] = a[u] * min(cnt[u][0], cnt[u][1]) * 2;for (int j : mp[u]){if (j == fu) continue;dfs1(j, u);}
}
void dfs2(int u, int fu, int minn)
{if (minn > a[u]){if (minn != inf){ans -= min(cnt[u][0], cnt[u][1]) * 2 * minn;}ans += dp[u];minn = a[u];}for (int j : mp[u]){if (j == fu) continue;dfs2(j, u, minn);}
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i] >> c[i];}for (int i = 1, u, v; i < n; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dfs(1, -1);if (cnt[1][0] != cnt[1][1]){cout << -1 << endl;return;}dfs1(1, -1);dfs2(1, -1, inf);cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}