树形DP + 贪心

时间复杂度 $O(nlogn)$

/* 2024/4/18  AC(IOI) 50/400ms
写了一个下午，终于A掉了，加号写成减号实在是无敌了，段错误还找了半个小时
写题还得是保持绝对专注，不然容易写的跟想的不一样
link: https://pintia.cn/problem-sets/994805046380707840/exam/problems/1649748772845703169?type=7&page=1
*/
#include <bits/stdc++.h>

// #define int long long

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f; 

int n;
int a[N], w[N];  // 数组a记录初始颜色， w记录改变需要的代价
vector<int> g[N];   // 树
int f[N][3], num[N];  
// f[i][0]: (以i为根的树)0比1恰好多1, f[i][1]: 1比0恰好多1, f[i][2]: 1和0一样多
// num[i]: 以i为根的树的结点数量(包括i)

void dfs(int u)
{
    num[u] = 1;
    if (g[u].size() == 0)
    {
        // cout << w[u] << endl;
        if (a[u] == 0) f[u][1] = w[u];
        else f[u][0] = w[u];
        return;
    }

    for (auto v : g[u]) dfs(v);

    // sum 记录某个合法方案所需要的代价总和
    int sum = 0;
    vector<int> q;
    for (auto v : g[u]) 
    {
        num[u] += num[v];
        // 如果子树的结点数量为偶数，只有f[i][2]是合法的，把它加入到sum中
        if (num[v] % 2 == 0) sum += f[v][2];
        else
        {
            // 这里先假设我们全部取0，后续在对sum进行(-f[v][0]+f[v][1])使得将选0修改成选1
            sum += f[v][0];
            q.push_back((f[v][1] - f[v][0]));
        }
    }

    sort(q.begin(), q.end());

    // 由于只能恰好多1少1或不变，我们必须将1加回来，使0和1的数量差不超过2
    int m = q.size() / 2;
    for (int i = 0; i < m; i ++ ) sum += q[i];

    // 如果当前是奇数，那么子树的和肯定是偶数，也就是 偶数个结点数量为奇数的子树
    // 当前选择了最优的一半0一半1 
    if (num[u] % 2)
    {
        // 子树的0和1数量相等
        f[u][0] = sum + (a[u] != 0) * w[u];
        f[u][1] = sum + (a[u] != 1) * w[u];

        // 子树的0和1的数量差为2
        // 注意这里必须判断q.size()是否为0，否则会segment fault
        // 因为如果所有子树的结点数量都是偶数，它们0和1的数量必然相等，不可能使得0和1的差为2
        if (m) f[u][0] = min(f[u][0], sum - q[m-1] + (a[u] != 1) * w[u]);
        if (m) f[u][1] = min(f[u][1], sum + q[m] + (a[u] != 0) * w[u]);

    } 
    // 如果当前是偶数，那么肯定有 奇数个奇数的子树
    // 要么0比1多1，这一位选1; 要么反过来，这一位选0
    else
    {
        f[u][2] = min((a[u] != 1) * w[u], q[m] + (a[u] != 0) * w[u]);
        f[u][2] += sum;
    }

}

void solve()
{
    cin >> n;
    vector<bool> fa(n+10);
    for (int i = 1; i <= n; i ++ )
    {
        int k;
        cin >> a[i] >> w[i] >> k;
        while (k -- )
        {
            int t;
            cin >> t;
            fa[t] = true;
            g[i].push_back(t);
        }
    }

    int u;
    for (int i = 1; i <= n; i ++ )
    { 
        if (!fa[i]) u = i;
    }


    dfs(u);

    if (num[u] % 2) cout << min(f[u][0], f[u][1]) << '\n';
    else cout << f[u][2] << '\n';


    // cout << "-------------" << endl;
    // for (int i = 1; i <= n; i ++ ) 
        // cout << i << ": " << f[i][0] << ' ' << f[i][1] << ' ' << f[i][2] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T -- )
    {
        solve();
    }
    return 0;
}