Tree Decoration

题号 NC24623
名称 Tree Decoration
来源 USACO

题目描述

给你一棵有根树，根节点为1，第i个节点有ci，ti两个值ci表示以第i个节点为根节点的子树装饰物的数量至少为ci，ti表示往第i个节点挂上一个装饰物需要ti的时间，问在满足所有ci的条件下，最少的花费时间是多少？

样例

输入
5 
-1 9 3 
1 2 2 
5 3 2 
5 1 4 
2 3 3 
输出
20

               1 
               |
               2
               |
               5
              / \
             4   3
样例中树的形状：
最优的情况是：
总花费为 20:

            1 [0/9(0)]
            |                     
            2 [3/9(6)]
            |
            5 [0/6(0)]
           / \
 [1/1(4)] 4   3 [5/5(10)]
 节点4和3分别需要挂1个和5个装饰物，而第5个节点因为子树内部已经满足个
数的要求所以可以不用挂装饰物，第2个节点只需要挂3个装饰物即可满足c2，最后第一个节点也不需要挂

算法

(贪心)

贪心的思路是,对树进行dfs，首先递归求出除当前节点作为根节点的子树中除根节点外要满足子树内部所有节点要求的最小时间是多少，并且维护子树内部挂上一个装饰物最小的耗时T是多少，然后判断当前根节点的ci是否被满足如果满足就回溯，如果没有就加上用T的时间乘上不足的部分，就能得到最短耗时的。

时间复杂度 O(N)

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
const int N = 100010;
typedef long long LL;
vector<int> v[N];
int c[N],t[N],g[N];
LL s[N];
bool st[N];
LL ans;
int n;

void dfs(int u)
{
    g[u] = t[u];
    for(int i = 0;i < v[u].size();i ++)
    {
        int j = v[u][i];
        dfs(j);
        g[u] = min(g[u],g[j]);
        s[u] += s[j];
    }
    if(s[u] < c[u])
    {
        ans += 1ll * g[u] * (c[u] - s[u]);
        s[u] = c[u];
    }
}

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

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(500);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}