3月9日Tree Decoration

题解：

对于叶子节点，我们直接购买要求购买的个数即可
然后树上维护几个变量，sz表示该节点的子树已经挂在了多少个礼物了，如果挂载的礼物总数小于要求的总数，那么当前结点是要必须再购买一些礼物的，但是并不一定买在当前结点上，我们可以买在他已经他子树上，找一个最便宜的结点来购买礼物，从而保证价格最低！这个我们就需要维护另一个变量imin，表示当前结点包含的所有子树价格最低的是多少。

代码：

//#pragma GCC optimize(3 , "Ofast" , "inline")

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define endl '\n'
#define int long long
const int maxn=2e5+10;
const int mod=1e9+7;


vector<int> edge[maxn];
int cnt[maxn];
int sz[maxn],ans,imin[maxn];

void dfs(int x){
    if(edge[x].size()==0){
        ans+=imin[x]*cnt[x];
        sz[x]=cnt[x];
        return ;
    }
    else{
        for(auto i:edge[x]){
            dfs(i);
            sz[x]+=sz[i];
            imin[x]=min(imin[x],imin[i]);
        }
        if(sz[x]<cnt[x]){
            ans+=imin[x]*(cnt[x]-sz[x]);
            sz[x]=cnt[x];
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    memset(imin,0x7f,sizeof imin);
    for(int i=1;i<=n;i++){
        int fa;
        cin>>fa>>cnt[i]>>imin[i];
        if(i!=1) edge[fa].push_back(i);
    }
    dfs(1);
    cout<<ans<<endl;

}