LC968 AC

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    using pii = pair<int, int>;
    using a3 = array<int, 3>;
    a3 dfs2(TreeNode* node) {
        if (node == nullptr) {
            return {0, 0, INT_MAX / 2};
        }
        a3 ret = {0, 0, 0};
        // ret[0]: all nodes below u are covered except u
        // ret[1]: all nodes below u are covered, including u, and no camera at u
        // ret[2]: all nodes below u are covered, including u, and there's a camera at u
        auto child = vector<TreeNode*>{node->left, node->right};
        int max_val = 0;
        int min_delta = INT_MAX / 2;
        for (auto v: child) {
            auto [subtree, cover_noplace, cover_place] = dfs2(v);
            ret[0] += cover_noplace;

            ret[1] += min(cover_noplace, cover_place);
            max_val = max(max_val, cover_noplace);
            min_delta = min(min_delta, cover_place - cover_noplace);

            ret[2] += min({subtree, cover_noplace, cover_place});
        }
        // ret[1] -= max_val;
        if (min_delta > 0) ret[1] += min_delta;
        ret[2] += 1;
        printf("u:%p %d,%d,%d\n", node, ret[0], ret[1], ret[2]);
        return ret;
    }
public:
    int minCameraCover(TreeNode* root) {
        auto ans = dfs2(root);
        return min(ans[1], ans[2]);
    }
};