洛谷P3018 [USACO11MAR]树装饰Tree Decoration
树形DP
因为要求最小，我们就贪心地用每个子树中的最小cost来支付就行了
1 #include <bits/stdc++.h>
2 #define For(i, j, k) for(int i=j; i<=k; i++)
3 #define Dow(i, j, k) for(int i=j; i>=k; i--)
4 #define LL long long
5 using namespace std;
6 inline int read() {
7 int x = 0, f = 1;
8 char ch = getchar();
9 while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch = getchar(); }
10 while(ch>='0'&&ch<='9') { x = x*10+ch-48; ch = getchar(); }
11 return x * f;
12 }
13
14 const int N = 1e5+11;
15 int n, nedge;
16 int Mn[N], fa[N], head[N], need[N];
17 LL f[N], have[N];
18 struct edge{
19 int to, pre;
20 }e[N*2];
21
22 inline void add(int x,int y) {
23 e[++nedge].to = y;
24 e[nedge].pre = head[x];
25 head[x] = nedge;
26 }
27
28 void dfs(int u) {
29 for(int i=head[u]; i; i=e[i].pre) {
30 int v = e[i].to;
31 if(v == fa[u]) continue;
32 dfs( v );
33 have[u] += have[v];
34 Mn[u] = min(Mn[u], Mn[v]);
35 f[u] += f[v];
36 }
37 if(need[u] > have[u]) {
38 f[u] = f[u]+1ll*(need[u]-have[u])*Mn[u];
39 have[u] = need[u];
40 }
41 }
42
43 int main() {
44 n = read();
45 For(i, 1, n) {
46 fa[i] = read();
47 need[i] = read();
48 Mn[i] = read();
49 if(fa[i] != -1) add(i, fa[i]), add(fa[i], i);
50 }
51 dfs(1);
52 printf("%lld\n",f[1]);
53 return 0;
54 }
转载于:https://www.cnblogs.com/third2333/p/8444558.html