提交记录

题目

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1.5e3+5,mod=1e9+7;

ll dp[3][N], s[N];
// dp[0][i] : i 由自己覆盖
// dp[1][i] : i 由儿子覆盖
// dp[2][i] : i 由父亲覆盖

vector<int> mp[N];

void dfs(int u, int fa){
    ll flg = 1e18;
    dp[0][u] = s[u];
    dp[1][u] = 1e18;
    for(auto x : mp[u])if(x != fa){
        if(dp[1][u] == 1e18){dp[1][u] = 0;}
        dfs(x, u);
        dp[0][u] += min({dp[0][x], dp[1][x], dp[2][x]});
        dp[2][u] += min(dp[0][x], dp[1][x]);
        if(dp[1][x] >= dp[0][x]){
            dp[1][u] += dp[0][x];
            flg = -1;
        }
        else{
            dp[1][u] += dp[1][x];
            flg = min(flg, dp[0][x] - dp[1][x]);
        }
    }
    if(flg != 1e18 && flg != -1){dp[1][u] += flg;}
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int u, m;
        cin>>u>>s[i]>>m;
        for(int j=1;j<=m;j++){
            int v;cin>>v;
            mp[u].push_back(v);
            mp[v].push_back(u);
        }
    }
    dfs(1, 0);
    cout<<min(dp[0][1], dp[1][1])<<"\n";
    return 0;
}