思路与算法

把宫殿看作带费用的树顶点支配问题。对u设三态：0为u放侍卫；1为u不放且至少有一个孩子放；2为u不放、暂由父亲照看。先迭代建父子顺序，再逆序计算。0态取每个孩子三态最小；2态取孩子0/1最小；1态在同样和上增加使至少一个孩子选0的最小差价。根只可取0/1。

正确性说明

守卫只能覆盖自己和相邻顶点。u放时孩子可以由u覆盖，三态均合法；u不放时不能让孩子等候u，因此孩子只能0/1。状态1还须至少一个孩子0，先各自取最优再强制一个孩子0的最小增量恰好覆盖此条件。各孩子子树互不相交，可独立求和，逐子树归纳得到最优费用。根没有父亲，排除状态2。

复杂度

O(nD)时间、O(nD)空间，D为总费用的十进制位数；包括输入、父子表、迭代遍历和三态初始化。

易错点

这是照看所有宫殿顶点，不是覆盖所有道路的另一道战略游戏。叶子的状态1不可行，用总费用+1作为精确上界哨兵。费用位数未给上限，使用内置大整数；迭代遍历避免深链递归栈。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> ch(n);
    vector<cpp_int> w(n);
    vector<int> par(n, -1);
    for (int k = 0; k < n; k++) {
        int u, m;
        cin >> u;
        --u;
        cin >> w[u] >> m;
        while (m--) {
            int v;
            cin >> v;
            --v;
            ch[u].push_back(v);
            par[v] = u;
        }
    }
    int root = find(par.begin(), par.end(), -1) - par.begin();
    vector<int> order{root};
    for (int i = 0; i < (int)order.size(); i++)
        for (int v : ch[order[i]])
            order.push_back(v);
    vector<array<cpp_int, 3>> dp(n);
    cpp_int INF = 1;
    for (auto v : w)
        INF += v;
    for (int z = n - 1; z >= 0; z--) {
        int u = order[z];
        cpp_int chosen = w[u], parent = 0, child = 0, extra = INF;
        for (int v : ch[u]) {
            chosen += min(dp[v][0], min(dp[v][1], dp[v][2]));
            cpp_int b = min(dp[v][0], dp[v][1]);
            parent += b;
            child += b;
            extra = min(extra, dp[v][0] - b);
        }
        dp[u][0] = chosen;
        dp[u][1] = child + extra;
        dp[u][2] = parent;
    }
    cout << min(dp[root][0], dp[root][1]) << "\n";
}