【每日一题】3月9日Tree Decoration

题意

约翰在装饰他家的一颗春分树（不是知道是啥），树上有 个节点，第一个节点是根，其余节点都有唯一的父节点，第个节点的父节点是,由于根节点没有父节点，记作-1

约翰可以往每个节点上挂装饰物，但是费用是变化的，在第个节点上挂一个装饰物需要花费元钱，要求以为根的子树上必须有个装饰物，然后问在哪些节点上挂装饰物，才能满足要求，并且使得装饰费用最少

直接从最底下开始dfs就可以了

最底下的一定是要挂的 因为最底下的就没有子树了 因此我们从最底下开始

够了的话就不用选

不够的话就下去更新数量

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
ll c[N] , t[N] , ans , sz[N];
ll n;
vector<int> edge[N];

void dfs(int u){
    for(auto& v : edge[u]){
        dfs(v);
        sz[u] += sz[v];
        t[u] = min(t[u] , t[v]);
    }
    if(sz[u] < c[u]){
        ans += (c[u] - sz[u]) * t[u];
        sz[u] = c[u];
    }
}

void solve(){
    scanf("%lld" , &n);
    ll fa;
    for(int i = 2 ; i <= n ; ++i){
        scanf("%lld" , &fa);
        scanf("%lld%lld" , &c[i] , &t[i]);
        if(fa == -1)    continue;
        edge[fa].push_back(i);
    }
    dfs(1);
    printf("%lld\n" , ans);
}

int main(void){
    solve();
    return 0;
}