守护二叉树

思路与复杂度

在逆序遍历中令 f[u][0] 为不选u的最优值，f[u][1] 为选u的最优值。不选u时，每个孩子可自由取两状态最大值；选u时，孩子只能不选。左右子树独立，覆盖两种互斥状态即可得到最优值。时间和空间 O(n)，用64位整数并避免深递归。

正确性与边界

根节点选与不选构成完整分类，每种分类下左右子树可独立取最优。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

long long a[N];
long long dp[N][2];
int leftSon[N], rightSon[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        cin >> leftSon[i] >> rightSon[i];
    }

    vector<int> order;
    stack<int> st;
    st.push(1);

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        order.push_back(u);

        if (leftSon[u] != 0) {
            st.push(leftSon[u]);
        }
        if (rightSon[u] != 0) {
            st.push(rightSon[u]);
        }
    }

    reverse(order.begin(), order.end());

    for (int u : order) {
        dp[u][0] = 0;
        dp[u][1] = a[u];

        int l = leftSon[u];
        int r = rightSon[u];

        if (l != 0) {
            dp[u][0] += max(dp[l][0], dp[l][1]);
            dp[u][1] += dp[l][0];
        }

        if (r != 0) {
            dp[u][0] += max(dp[r][0], dp[r][1]);
            dp[u][1] += dp[r][0];
        }
    }

    cout << max(dp[1][0], dp[1][1]) << "\n";

    return 0;
}