题意

• 以p(父亲),c(需要挂的最少装饰物个数),t(挂一个装饰物需要的时间)的形式输入每一个树上的节点。
• 问满足每一个节点的装饰物需求最少需要多少时间

思路

• 对于叶子节点i，他上面至少悬挂c[i]个装饰物
• 对于其它节点j，如果他的子节点累计挂的装饰物已经大于等于c[j]，则什么都不用做，如果不够的话，就给总消耗时间加上[c[j]-sum(子树悬挂装饰物总和)]*min(子节点最小悬挂时间)

注意

• 注意树的建立，用邻接矩阵
• 注意dfs方式，先递归到头，回溯的时候在判断是否足够

AC代码

#include<bits/stdc++.h>
using namespace std;
int p[101010],t[101010];
long long c[101010];
vector<int> tre[101010];
long long ans;
long long dfs(int idx,int fa){
    long long sum=0;//记录挂了多少个了
    //往下走
    for(auto &i:tre[idx]){
        if(i==fa) continue;
        sum+=dfs(i,idx);
        t[idx]=min(t[idx],t[i]);//更新整棵树的最小t
    }
    if(sum<c[idx]){//没挂够/到底了
        ans+=(c[idx]-sum)*t[idx];
        return c[idx];
    }
    return sum;
}
int main(){
    int n;
    scanf("%d",&n);
    int root;
    for(int i=1;i<=n;i++){
        scanf("%d%lld%d",&p[i],&c[i],&t[i]);
        if(p[i]==-1) root=i;
        else{
            tre[p[i]].push_back(i);
            tre[i].push_back(p[i]);
        }
    }
    dfs(root,-1);
    printf("%lld",ans);
    return 0;
}
···