算法1

树形dp $O(n^2)$

本蒟蒻第一次做的时候没有考虑到 可以用dp[x][0] 去维护父节点的性质
所以直接两边dfs 暴力换根做的 (码量属实多想的也多属实不如考虑父节点的方法简单)
但是毕竟看到别人的题解都一摸一样 提供一个不一样的思路.

dp[x][0] 表示不选择 x 同时x 也没有被儿子选择的最小值(只有x 没有被选择其他均被选择)
dp[x][1] 表示不选择x 但是x 被儿子选择的最小值
dp[x][2] 表示选择 x 的最小值
设儿子节点是 t (这里是要求和)
dp[x][0] = dp[t][1]
dp[x][1] = min(dp[t][1], dp[t][2])
dp[x][2] = min(dp[t][0], dp[t][1], dp[t][2]) + a[x]

那么这么做只能获得根节点的全部信息， 怎么获得所有点的信息呢？
类似求树的中心再来一边 dfs 然后换根//
首先需要知道父节点对你的贡献是什么
假设你是x 你的父亲是 fa
那么dp[fa][0] 对你的贡献应该是 dp[fa][0] - dp[x][1]
类似的思路 dp[fa][2] 对你的贡献也好考虑 最终就是 dp[fa][2] - min(dp[x][0], min(dp[x][1], dp[x][2]));
可是比较难思考的就是 dp[fa][1] 对你的贡献
那么此时你就有两种可能
1 fa 节点的1 是由你看守提供的
2 fa 节点的1 不是由你看守提供的
对于情况2 很简单 dp[fa][1] - min(dp[x][1], dp[x][2]);(也就跟前面一样)
对于情况1 需要维护一个数组 num[fa] 来表示fa 的子节点跟新的最小值的节点
然后如果你恰好是这个节点 。、。。 那么不能单纯的减去你
因为可能除去你之外 也有别的 和 除去你之外 没有别的两种情况.. 所以还得维护一个次小值
然后根据次小值的 情况 最终求出 dp[fa][2] 对你的贡献....
(具体实现看代码。。)

求出这三个东西之后就可以把父亲的节点当成子节点去更新你的解了
然后通过换根就能求出所有节点为根的情况 取 min(dp[x][1], dp[x][2])即可

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
struct Node {
    int to, nex;
}edge[maxn << 3];
int head[maxn], cnt;
void add(int l, int r) {
    edge[++cnt].nex = head[l];
    edge[head[l] = cnt].to = r;
}
long long dp[maxn][3];
// 记录不选择第 i 个点但是第 i 个点又是被看守的状态的时候 故意亮的看守是谁
// -1 表示 不存在（即所有点的选择都是min） x 表示 将x 这个子节点专门选择 
// used 表示最小值, used2 表示次小值
int used[maxn], used2[maxn];
void dfs1(int fa, int x) {
    used[x] = -1;
    long long min_ = 1ll << 60, pos = -1;
    long long min_2 = 1ll << 60, pos2 = -1; 
    for (int i = head[x]; i; i = edge[i].nex) {
        int to = edge[i].to;
        if (to == fa) continue;
        dfs1(x, to); 
        dp[x][0] += dp[to][1];
        // 维护最大值和次大值 
        if (min_ >= dp[to][2] - dp[to][1]) {
            min_2 = min_;
            pos2 = pos;
            min_ = dp[to][2] - dp[to][1];
            pos = to;
        } else if (min_2 >= dp[to][2] - dp[to][1]) {
            min_2 = dp[to][2] - dp[to][1];
            pos2 = to;
        }
        dp[x][1] += min(dp[to][1], dp[to][2]);
        dp[x][2] += min(dp[to][0], min(dp[to][1], dp[to][2]));
    }
    // 因为我亮着一定要加上自己的花费 
    dp[x][2] += a[x]; 
    // 次大值就是 pos2 那么如果 used[x] = -1 那么used2[x] 必定等于-1
    // 如果 used[x] != -1 那么used2[x] 还有可能等于-1 
    used2[x] = pos2;
    used[x] = pos;
    // 表示没有找见一个点可以亮着
    if (min_ > 0) {
//      cout << "需要增加 哈" << endl; 
    if (pos == -1) { 
//      cout << x << " 没有儿子节点" << endl; 
            // 如果根本没有子节点
            // 那么就设为最大，以后一定不会用到 
        dp[x][1] = (1 << 30);
    } else {
            // 那么就把最小的这个的差值加上 
        dp[x][1] += abs(dp[pos][1] - dp[pos][2]);
    }
    }
//  cout << x << " " << dp[x][0] << ' ' << dp[x][1] <<  " " << dp[x][2] << endl;
}
// 这里的话要用 父节点去更新儿子节点 
void dfs2(int fa, int x, long long &ans) {
    // 因为此时 的 x 是父亲
    // 所以 可以直接更新答案 
    ans = min(ans, dp[x][1]);
    ans = min(ans, dp[x][2]);
    for (int i = head[x]; i; i = edge[i].nex) {
        int to = edge[i].to;
        if (to == fa) continue;

        // 分别记录父亲的节点除去我这子节点之后剩余的值 
        long long fu1 = dp[x][1], fu0, fu2;
        // 表示父亲的这个节点我贡献了多少 
        int jian = min(dp[to][0], min(dp[to][1], dp[to][2]));
        fu2 = dp[x][2] - jian;
        // 因为父亲不选择那么我只能选择 dp[to][1]这种 
        fu0 = dp[x][0] - dp[to][1];
        // 下面这个是看dp[x][1] 在不包含儿子to 的情况下到底等于多少 

        // 表示父亲的不亮灯只有从你这里获得的 
        if (used[x] == to) {
            // 那么也就意味这 fu1 选择是亮灯的你 
            fu1 -= dp[to][2]; 
            // 这里的话 还需要看一下 当前的状态是否可行
            if (used2[x] == -1) {
                // 如果次小值不存在 那么我就是正无穷不会用到 
                fu1 = 1 << 30;
            } else {
                // 否则次小值存在这时要看当时的选择是什么
                if (dp[used2[x]][1] < dp[used2[x]][2]) {
                    // 如果当时选择的是 1那么还需要转换成 2
                    fu1 += abs(dp[used2[x]][1] - dp[used2[x]][2]);
                } 

            }
        } else {
            // 否则 fu1 选择的是灭灯的你
            fu1 -= min(dp[to][1], dp[to][2]); 
        }

        //dp[to][1] = min 父亲选择 + 儿子选择或不选择
        // 或者 父亲不选择 + 儿子选择 

        dp[to][1] = min(fu2 + min(dp[to][1], dp[to][0]),
        fu1 + dp[to][1]);
        // dp[to][0] = 父亲不选择 + 原先的 dp[to][0] 
        dp[to][0] += fu1; 
        // dp[to][2] = 父亲的三种取最少 
        dp[to][2] += min(fu0, min(fu1, fu2)); 
//      puts("-----------------------------------------------------------------");
//      cout << x << " " << used[x] << ' ' << used2[x] << endl;
//      cout << x << ' ' << fu0 << ' ' << fu1 << ' ' << fu2 << endl;
//      cout << to << ' ' << dp[to][0] << " " << dp[to][1] << " " << dp[to][2] << endl;
//      puts("-----------------------------------------------------------------");
        dfs2(x, to, ans);
    }

}  
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        int l, k, m;
        scanf("%d%d%d", &l, &k, &m);
        a[l] = k;
        for (int j = 1, r; j <= m; ++j) {
            scanf("%d", &r);
            add(l, r);
            add(r, l);
        }
    }
    dfs1(-1, 1); 
    long long answer = (1ll << 60);
    dfs2(-1, 1, answer);
    cout << answer << endl;
    return 0;
}