# 11082: 【原1082】二哥的鹅塘

### 题目描述

author: duruofei 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1082

## Description

“鹅鹅鹅”事件过后，二哥为他的鹅们建立了庞大的鹅塘。

## Sample Input

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0


## Sample Output

25


## FineArtz's solution

/* 二哥的鹅塘 */
#include <iostream>
#include <set>
using namespace std;

const int INF = 2147483647;

class Node{
public:
int w = 0;
set<int> child;
};

Node a[100005];
int n, root = 0;
int f[100005][3] = {0};
bool b[100005] = {0};

void dp(int x){
int t = INF;
for (int i : a[x].child){
dp(i);
f[x][0] += min(min(f[i][0], f[i][1]), f[i][2]);
f[x][1] += min(f[i][0], f[i][1]);
f[x][2] += min(f[i][0], f[i][1]);
t = min(t, f[i][0] - min(f[i][0], f[i][1]));
}
f[x][0] += a[x].w;
f[x][1] += t;
}

int main(){
cin >> n;
for (int i = 1; i <= n; ++i){
int x, w, c;
cin >> x >> w >> c;
a[x].w = w;
for (int i = 1; i <= c; ++i){
int y;
cin >> y;
a[x].child.insert(y);
b[y] = true;
}
}
for (int i = 1; i <= n; ++i){
if (!b[i]){
root = i;
break;
}
}
dp(root);
cout << min(f[root][0], f[root][1]) << endl;
return 0;
}