星际能量矩阵：树形 DP 的递归与非递归双解

在算法竞赛和工程开发中，处理树形结构上的最大独立集（Maximum Independent Set）及其变种问题是非常经典的。

今天我们不谈无聊的“上司与下属”，而是来解决一个星际级别的工程难题——能量矩阵的过载保护。我们将对比两种解法：DFS 递归和BFS非递归（防爆栈）。

题目背景：能量矩阵的共振干扰

题目名称：星际能量矩阵

【背景描述】你是一座巨型空间站的首席能源工程师。空间站的能源系统由 N 个能量核心（编号 1∼N）组成。这些核心之间通过光缆连接，形成了一个严密的树状网络，其中 1 号核心是主反应堆（根节点）。

除了主反应堆外，每个核心都有且仅有一个“上级供能节点”（父节点）。

每个能量核心 i 都有一个固定的额定功率ai​。现在你需要激活这些核心来为空间站供电。但是，系统存在一个致命的物理缺陷：“相位共振”。

规则：如果一个能量核心和它的直连上级节点同时被激活，它们之间会产生剧烈的相位共振，导致线路熔断。简单来说：相邻的父子节点不能同时被激活。

【你的任务】在不触发“相位共振”的前提下（即任意一条连接线两端的节点不能同时被选），制定一个激活方案，使得所有被激活核心的总功率之和最大。

【输入格式】

• 第一行：一个整数 N（核心总数）。

• 第二行：N−1 个整数，第 i 个数表示第 i+1 号核心的上级节点（父节点）。

• 第三行：N 个整数，表示每个核心的额定功率 a[i]​。

【输出格式】

• 一个整数，表示能获得的最大总功率。

算法核心：树形 DP

这个问题本质上是在树上做决策：每个节点只有“激活”和“不激活”两种状态。

我们定义状态数组dp[u][0/1]：

• dp[u][0]：表示不激活节点 u 时，以 u 为根的子系统能提供的最大功率。

• dp[u][1]：表示激活节点 u 时，以 u 为根的子系统能提供的最大功率。

状态转移方程（决策逻辑）：

1. 如果不激活当前节点 u (dp[u][0])：它的子节点 v 就失去了限制，可以激活，也可以不激活。为了总功率最大，我们对每个子节点取两种情况的最大值并累加。

   dp[u][0]+=max(dp[v][0],dp[v][1])

2. 如果激活当前节点 u (dp[u][1])：为了防止共振，它的子节点 v绝对不能激活。

   dp[u][1]+=dp[v][0]

   别忘了加上 u 自身的功率 au​。

解法一：DFS 递归

这是最符合人类思维的写法。利用 DFS 的“回溯”特性，先深入到最底层的叶子节点，算好后一层层向上汇报。

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int maxn=100010; int n; int a[maxn]; // 核心功率 int h[maxn], vtex[maxn], nxt[maxn], idx; long long dp[maxn][2]; // 邻接表存图 void addedge(int u,int v){ vtex[idx]=v; nxt[idx]=h[u]; h[u]=idx++; } // 递归计算 inline void dfs(int x){ int p=h[x]; while(p!=-1){ int son=vtex[p]; dfs(son); // 【递】先去计算子节点 // 【归】状态转移 // 1. x 不激活，子节点随意（选最大的） dp[x][0]+=max(dp[son][0],dp[son][1]); // 2. x 激活，子节点必须静默 dp[x][1]+=dp[son][0]; p=nxt[p]; } dp[x][1]+=a[x]; // 激活 x，加上自身的功率 } int main(){ cin>>n; memset(h,-1,sizeof(h)); for(int i=2;i<=n;i++){ int x; cin>>x; addedge(x,i); } for(int i=1;i<=n;i++) cin>>a[i]; dfs(1); // 从主反应堆开始 cout<<max(dp[1][0],dp[1][1]); return 0; }

解法二：BFS + 逆序 DP

为了解决递归过深的问题，我们采用BFS来模拟递归过程。

核心思路：

1. BFS 拓扑排序：利用队列，将树按层级展开，存入vec数组。这样保证了父节点一定在子节点前面。

2. 逆序遍历：我们倒着遍历vec数组（从最后一个元素往前）。这相当于从叶子节点向根节点推进。当我们处理父节点时，它的所有子节点一定已经处理完了，数据是现成的。

#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstring> using namespace std; const int maxn=100010; int n; int a[maxn]; int h[maxn], vtex[maxn], nxt[maxn], idx; long long dp[maxn][2]; queue<int> q; vector<int> vec; // 关键：存储BFS的拓扑序列 void addedge(int u,int v){ vtex[idx]=v; nxt[idx]=h[u]; h[u]=idx++; } int main(){ cin>>n; memset(h,-1,sizeof(h)); for(int i=2;i<=n;i++){ int x; cin>>x; addedge(x,i); } for(int i=1;i<=n;i++) cin>>a[i]; // --- 第一步：BFS 建立层级顺序 --- q.push(1); // 主反应堆入队 vec.push_back(1); while(!q.empty()){ int tmp=q.front(); q.pop(); int p=h[tmp]; while(p!=-1){ int v=vtex[p]; q.push(v); vec.push_back(v); // 记录顺序：子节点永远在父节点后面 p=nxt[p]; } } // --- 第二步：逆序 DP (自底向上计算) --- // 倒序遍历 vec，相当于从树的边缘向中心汇聚 for(int i=n-1;i>=0;i--){ int u=vec[i]; // 取出当前要处理的核心编号 int p=h[u]; while(p!=-1){ // 遍历它的子节点 int v=vtex[p]; // 此时 v 一定已经计算完毕了，直接取值 // 1. u 不激活，v 可选最大值 dp[u][0]+=max(dp[v][1],dp[v][0]); // 2. u 激活，v 必须静默 dp[u][1]+=dp[v][0]; p=nxt[p]; } dp[u][1]+=a[u]; // 加上自身功率 } cout<<max(dp[1][0],dp[1][1]); return 0; }

总结