贸易网站建设,什么行业最需要网站建设,移动网站的建设,广州广告制作有限公司题目链接
Codeforces Round 646 (Div. 2) E. Tree Shuffling
思路
考虑一个节点 u u u#xff0c;显然它子树中的操作可以由它本身和祖先来进行。如果它的祖先有比它花费更小的#xff0c;直接跳过节点 u u u。
我们分别记录每一个子树中位置不对的 0 0 0和 1 1 1的个数显然它子树中的操作可以由它本身和祖先来进行。如果它的祖先有比它花费更小的直接跳过节点 u u u。
我们分别记录每一个子树中位置不对的 0 0 0和 1 1 1的个数每次操作选出较小的那一个即可。
代码
#include bits/stdc.h
using namespace std;
#define int long long
#define ull unsigned long long
typedef pairint, 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];
vectorintmp[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;
}
