树重着色技术问询：如何在约束下最大化红色顶点数量？

这个问题可以通过树形动态规划高效解决，时间复杂度为O(n)，完全适配50000个顶点的规模。核心思路是利用树的递归结构，通过后序遍历维护每个节点的两种状态，从而推导出全局最优解。

状态定义 #

对每个节点u，定义两个状态：

• dp[u][0]：以u为根的子树中，u最终为蓝色时，子树能保留的最大红色顶点数。
• dp[u][1]：以u为根的子树中，u最终为红色时，子树能保留的最大红色顶点数。

状态转移规则 #

根据节点u的初始颜色，分两种情况处理：

1. 节点u初始为蓝色 #

蓝色顶点无法转为红色，因此dp[u][1]不可行（可设为负无穷表示无效）。

• dp[u][0]：u保持蓝色，每个子节点v可以选择最优状态（保留红色或转为蓝色），取所有子节点状态的最大值之和：
  dp[u][0] = sum(max(dp[v][0], dp[v][1]) for v in u的子节点)

2. 节点u初始为红色 #

• dp[u][1]：u保留红色，那么所有子节点必须转为蓝色（避免相邻红顶点），总和为1（u自身）加上所有子节点dp[v][0]的和：
  dp[u][1] = 1 + sum(dp[v][0] for v in u的子节点)
• dp[u][0]：u转为蓝色，每个子节点v可以选择最优状态，取所有子节点状态的最大值之和：
  dp[u][0] = sum(max(dp[v][0], dp[v][1]) for v in u的子节点)

遍历与计算 #

采用后序遍历处理树（先处理所有子节点，再处理父节点），确保计算父节点状态时，子节点的状态已确定：

1. 用邻接表存储树结构（适配大规模节点）。
2. 递归或迭代执行后序遍历，计算每个节点的dp[u][0]和dp[u][1]。
3. 最终结果取根节点的最优状态：
   • 若根节点初始为蓝色，结果为dp[root][0]。
   • 若根节点初始为红色，结果为max(dp[root][0], dp[root][1])。

细节处理 #

• 初始相邻红顶点的情况会被自动处理：当父子节点均为红色时，要么父节点转蓝（子节点可保留红），要么子节点转蓝（父节点保留红），DP会选择总红数更大的方案。
• 对于链状树等深度极大的情况，建议用迭代后序遍历避免递归栈溢出。

伪代码示例 #

def calculate_max_red(color, adj):
    n = len(color)
    # 用迭代后序遍历避免栈溢出
    stack = [(0, -1, False)]  # (节点, 父节点, 是否已处理)
    dp = [[0, -float('inf')] for _ in range(n)]  # dp[u][0], dp[u][1]

    while stack:
        u, parent, processed = stack.pop()
        if not processed:
            stack.append((u, parent, True))
            # 压入子节点（逆序保证遍历顺序正确）
            for v in reversed(adj[u]):
                if v != parent:
                    stack.append((v, u, False))
        else:
            if color[u] == 'blue':
                dp0 = 0
                for v in adj[u]:
                    if v == parent:
                        continue
                    dp0 += max(dp[v][0], dp[v][1])
                dp[u][0] = dp0
            else:
                dp0 = 0
                dp1 = 1
                for v in adj[u]:
                    if v == parent:
                        continue
                    dp0 += max(dp[v][0], dp[v][1])
                    dp1 += dp[v][0]
                dp[u][0] = dp0
                dp[u][1] = dp1

    if color[0] == 'blue':
        return dp[0][0]
    else:
        return max(dp[0][0], dp[0][1])

内容的提问来源于stack exchange，提问作者alsv777