编辑代码

class TreeNode:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children if children else []

def min_dominating_set(root):
    from math import inf

    def dfs(node):
        if not node.children:  # 叶子节点
            return (1, 0, inf)
        
        dp0, dp1, dp2 = 1, 0, 0
        min_diff = inf
        has_selected = False

        for child in node.children:
            c0, c1, c2 = dfs(child)
            # 更新状态0: 选中当前节点，子节点取最小值
            dp0 += min(c0, c1, c2)
            # 更新状态1: 未选当前节点但被父覆盖，子节点须被选或被子覆盖
            dp1 += min(c0, c2)
            # 处理状态2的中间计算
            current_min = min(c0, c2)
            dp2 += current_min
            # 检查是否有子节点被选中（c0更优）
            if c0 <= c2:
                has_selected = True
            # 计算替换代价
            diff = c0 - current_min
            if diff < min_diff:
                min_diff = diff
        
        # 处理状态2: 若所有子节点均未被选中，需强制替换一个
        if not has_selected:
            dp2 += min_diff
        
        return (dp0, dp1, dp2)

    if not root:
        return 0
    dp0, _, dp2 = dfs(root)
    return min(dp0, dp2)

# 示例测试
# 构造树：根节点A有两个叶子B和C
v_1 = TreeNode()
v_2 = TreeNode()
v_3 = TreeNode()
v_6 = TreeNode()
v_7 = TreeNode()
v_11 = TreeNode()
v_12 = TreeNode()
v_15 = TreeNode()

v_4 = TreeNode(children=[v_2, v_3])
v_5 = TreeNode(children=[v_1, v_4])
v_8 = TreeNode(children=[v_6, v_7])
v_9 = TreeNode(children=[v_5, v_8])
v_10 = TreeNode(children=[v_9])
v_13 = TreeNode(children=[v_11, v_12])
v_14 = TreeNode(children=[v_10,v_13,v_15])



print(min_dominating_set(v_14))  # 输出1（选中A）