有向无环图(DAG)节点可达和计算：解决重复计数与DP实现

问题核心 #

初始拓扑DP解法的错误在于直接累加子节点的答案，导致多个子节点共同可达的节点被重复计数。例如节点1的子节点2和3都能到达节点4，累加ans[2]和ans[3]会重复计算节点4的数值。

状态压缩DP解法（O(n*2^k + m)） #

利用k≤8的特性，采用逆序处理+状态压缩的方式避免重复计数：

1. 状态定义 #

逆序遍历节点（从n到1），对每个节点i维护一个数组dp[mask]，其中：

• mask是k位二进制数，第t位（0≤t<k）为1表示节点i+t+1的可达集合已被计入当前总和
• dp[mask]表示从i出发，加上mask标记节点的不重复可达节点总和

2. 初始状态 #

对节点i，初始仅包含自身数值：

dp[0] = beauty[i]

若i+t+1 > n，超出范围的节点对应的掩码位直接忽略。

3. 状态转移 #

遍历所有掩码mask，再遍历每个可能的t（0≤t<k）：

• 若mask的第t位为0，且存在边i→i+t+1（记j = i+t+1）：
  1. 计算新掩码：new_mask = mask | (1 << t)
  2. 计算子掩码：sub_mask = mask >> (t+1)（对应j之后的k-t-1个节点的覆盖状态）
  3. 转移公式：

     dp[new_mask] = max(dp[new_mask], dp[mask] + dp_j[sub_mask] - beauty[j])
     

     减去beauty[j]是因为dp_j[sub_mask]已包含j自身数值，避免重复计入。

4. 最终答案 #

节点i的答案ans[i]为dp数组中的最大值，即所有可能掩码对应的不重复总和的最大值：

ans[i] = max(dp[mask] for mask in range(2**k))

关键逻辑说明 #

• 逆序处理确保计算i时，所有j>i的节点状态已确定
• 掩码sub_mask传递了j之后节点的覆盖状态，避免重复计算j的可达集合中已被计入的部分
• 时间复杂度：每个节点处理2^k个状态，每条边处理一次，总复杂度O(n*2^k + m)，完全适配题目规模

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