题解 P3018 【[USACO11MAR]树装饰Tree Decoration】

Idvz · 2017-05-05 19:13:43 · 题解

可以用dfs递归找一找

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int SN = 100000 + 10;

LL f[SN], t[SN], c[SN], now[SN], head[SN];
LL n, ans, que[SN], num, root;

bool vis[SN];

struct Edge {
    int from,to,next;
}E[SN<<1];

void dfs(int u) {
    vis[u] = 1;
    for(int i = head[u]; i ;i = E[i].next) {
        if(vis[E[i].to])    continue;
        dfs(E[i].to);
        c[u] = min(c[u] , c[E[i].to]); //小贪心，更新树中最小的花费
        now[u] += now[E[i].to]; //更新一下当前以i为节点的子树中购买的个数
    }
    if(now[u] < t[u]) {
        ans += (t[u]-now[u]) * c[u]; //如果不够，接着买
        now[u] = t[u];
    }
}

void Add(int u,int v) {
    E[++num].from = u;
    E[num].to = v;
    E[num].next = head[u];
    head[u] = num;
}

int main() {

    scanf("%lld",&n);

    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld",&f[i],&t[i],&c[i]);
        if(f[i] != -1)
        Add(i,f[i]),Add(f[i],i); //加无向边
        else root = i;
    }

    dfs(root);

    printf("%lld\n",ans);

    return 0;

}