傻咯
写了半个下午的DP，在第四个点就WA了
还是逃不过看题解
DFS下推，将最小值尽可能下传覆盖，因为对于靠近叶子节点的点，既然顶端的花费比父亲的花费更小，我们当然选择上面更小的最优。
DFS上推返回直接求解，利用pair维护每个节点原先b状态1的个数以及所需c状态1的个数，如果某个节点二者均不为0，则意味着出现了min(cntb, cntc)对不匹配点。
此时，如果cost[now]相对于顶端花费更小，则将这点对处理掉，花费为 2 * min(cntb1, cntc1) * cost[now]，否则就留着上面再处理。
到达根节点并处理完毕，最好就是根节点的first和second都是0，则结果为各个节点花费的总和，开个全局变量统计一下就好；否则，说明整棵树的点无法达到c状态，输出-1。
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cmath>
5 #include<cstdio>
6 #include<vector>
7 #define ll long long
8 #define fi first
9 #define se second
10 using namespace std;
11 const int N = 2e5 + 10;
12 typedef pair<ll, ll> pii;
13
14 int n;
15 ll cost[N],b[N],c[N];
16 ll dp[N];
17 ll res = 0;
18
19 vector<int> t[N];
20
21 ll MIN(ll a, ll b)
22 {
23 return a < b ? a : b;
24 }
25
26 pii dfs(ll now, ll fa, ll mn)
27 {
28 pii tmp = make_pair(0, 0);
29 if(b[now] != c[now]){
30 if(b[now]){
31 tmp.fi++;
32 }else{
33 tmp.se++;
34 }
35 }
36 for(int i = 0 ; i < t[now].size() ; i++){
37 int son = t[now][i];
38 if(son == fa) continue;
39
40 pii k = dfs(son, now, MIN(mn, cost[now]));
41 tmp.fi += k.fi;
42 tmp.se += k.se;
43 }
44 if(cost[now] < mn){
45 ll take = MIN(tmp.fi, tmp.se);
46 res += 2ll * take * cost[now];
47 tmp.fi -= take;
48 tmp.se -= take;
49 }
50 return tmp;
51 }
52
53 int main(){
54 scanf("%d",&n);
55 for(register int i = 1 ; i <= n ; i++){
56 scanf("%lld%lld%lld",&cost[i],&b[i],&c[i]);
57 }
58 for(register int i = 1 ; i < n ; i++){
59 int u, v;scanf("%d%d",&u,&v);
60 t[u].push_back(v);
61 t[v].push_back(u);
62 }
63
64 pii ans = dfs(1, 0, 2e9);
65 if(ans.fi || ans.se){
66 printf("-1\n");
67 }else{
68 printf("%lld\n",res);
69 }
70
71 return 0;
72 }
原文：https://www.cnblogs.com/ecustlegendn324/p/13974641.html