树上贪心 E. Tree Shuffling 暑训第一天

题目大意：

给你一棵树，这棵树每一个点有三个值，分别是a,b,c，a表示这个点的权值，b表示这个点本来的值，c表示这个点想要变成的值（b和c都是0或者1），对于一棵子树u，你可以选择k个节点，然后这k个节点进行重新洗牌，花费是k*a[u]，问是否可以通过重新洗牌使得所有的节点都变成想要的节点，是则输出最小的花费，不是输出-1。

题解：

这个题目其实不是特别难，但是有点绕，一开始又想错了一部分，所以最后做的都想睡觉了。。。

这个维护一条链上的最小值，如果这个值是从根节点到现在位置的最小值，则更新所有可以更新的节点，如果不是则可知最小值在其祖先节点，从根节点开始维护最小值，从叶子节点开始更新。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
ll a[maxn],b[maxn],c[maxn],ans;
vector<int>G[maxn];
void add(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
}
void dfs1(int u,int pre,ll mins){
    mins=min(mins,a[u]);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==pre) continue;
        dfs1(v,u,mins);
        b[u]+=b[v];
        c[u]+=c[v];
    }
    if(a[u]==mins){
//        printf("b=%lld c=%lld
",b[u],c[u]);
        ll num = min(b[u],c[u]);
        ans+=num*2*a[u];
        b[u]-=num;
        c[u]-=num;
//        printf("u=%d pre=%d mins=%lld num=%lld ans=%lld b=%lld c=%lld
",u,pre,mins,num,ans,b[u],c[u]);
    }
}


int main(){
    int n;
    int f1=0,f2=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
        if(b[i]==c[i]) b[i]=c[i]=0;
        f1+=b[i],f2+=c[i];
    }
    if(f1!=f2){
        printf("-1
");
        return 0;
    }
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    ans=0;
    dfs1(1,0,inf64);
    printf("%lld
",ans);
    return 0;
}
/*
8
82 0 0
3 1 1
53 0 0
5 0 0
81 0 1
56 1 0
99 1 0
87 0 1
5 7
2 8
4 7
4 1
3 2
2 5
8 6
----
7
6 0 0
2 0 1
4 0 1
10 1 0
6 1 0
3 0 0
9 1 1
6 3
5 6
2 6
6 4
5 7
1 7

 */

树上贪心 E. Tree Shuffling 暑训第一天

推荐阅读