某岛

… : "…アッカリ~ン . .. . " .. .
March 10, 2020

Vijos P1144. 小胖守皇宫

二分图最小支配集。


//}/* .................................................................................................................................. */

const int N = int(1500) + 9;
LL f[N][3]; // 0: 被孩子支配
             // 1: 被自己支配
             // 2: 被父亲支配

LL w[N]; VI adj[N];
int n;


// f[u][2] += min(f[v][0], f[v][1]);
// f[u][1] += f[v][2]
// f[u][0] = f[u][2]   += delta

void dfs(int u = 1, int p = -1){

#define v adj[u][i]

    LL delta = INFF;

    for (int i=0;i<adj[u].size();++i) if (v != p){
        dfs(v, u);
        f[u][2] += min(f[v][0], f[v][1]);
        f[u][1] += f[v][2];
        checkMin(delta, f[v][1] - f[v][0]);
    }

    f[u][1] += w[u];
    f[u][0] = f[u][2] + max(0ll, delta);
    checkMin(f[u][2], f[u][1]);
    //assert(f[u][2] <= f[u][1]);
    //assert(f[u][2] <= f[u][0]);
}
#undef v

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    REP_1_C(i, RD(n)){
        int u; RD(u); RD(w[u]); Rush{
            int v; RD(v);
            adj[u].PB(v);
            adj[v].PB(u);
        }
    }

    dfs();

    cout << min(f[1][0], f[1][1]) << endl;
}