你好！我是你的OI教练。

这道题是树形 DP 的教科书级题目。代码并不长，但每一行都对应着状态转移方程的逻辑。

下面是符合 NOIP C++14 标准的竞赛代码。我在关键逻辑、易错点（如建图方向、找根节点）都加上了详细注释。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 数据规模分析：N <= 6000
// 快乐指数绝对值 <= 128，总和不会爆 int，但在更复杂的题目中要注意是否需要 long long
const int MAXN = 6005;

// r[i]: 第 i 号职员的快乐指数
int r[MAXN];

// dp[u][0]: u 不参加舞会，以 u 为根的子树最大快乐值
// dp[u][1]: u 参加舞会，以 u 为根的子树最大快乐值
int dp[MAXN][2];

// 邻接表存图，adj[u] 存储 u 的所有直系下属
vector<int> adj[MAXN];

// 辅助数组，用来标记谁有上司，方便最后找根节点
bool has_boss[MAXN];

// 核心 DFS 函数：进行树形 DP
void dfs(int u) {
    // 1. 初始化边界状态
    // 如果 u 不去，初始贡献为 0
    dp[u][0] = 0;
    // 如果 u 去，初始贡献为他自己的快乐值
    dp[u][1] = r[u];

    // 2. 遍历所有子节点（下属），自底向上计算
    for (int v : adj[u]) {
        dfs(v); // 递归先算子节点

        // 3. 状态转移
        
        // 情况 A: 上司 u 不去 (dp[u][0])
        // 此时下属 v 去不去都可以，为了利益最大化，取两者较大值累加
        dp[u][0] += max(dp[v][0], dp[v][1]);

        // 情况 B: 上司 u 去 (dp[u][1])
        // 题目限制：上司去了，直系下属 v 绝对不能去
        // 所以只能累加 v 不去时的最大值
        dp[u][1] += dp[v][0];
    }
}

int main() {
    // 优化 C++ 输入输出速度，竞赛标配
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    // 读入快乐指数
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }

    // 读入上下级关系
    // 注意：输入格式是 "L K"，代表 K 是 L 的上司
    // 建图方向应该是：上司 -> 下属 (K -> L)，这样方便 DFS 遍历子树
    for (int i = 1; i < n; i++) {
        int l, k;
        cin >> l >> k;
        
        adj[k].push_back(l); // K 是父，L 是子
        has_boss[l] = true;  // 标记 L 有上司
    }

    // 关键点/易错点：寻找根节点
    // 题目没有直接给出根节点，根节点是全公司唯一没有上司的人
    int root = 0;
    for (int i = 1; i <= n; i++) {
        if (!has_boss[i]) {
            root = i;
            break;
        }
    }

    // 从根节点开始进行树形 DP
    dfs(root);

    // 最终答案：根节点去或不去，取最大值
    cout << max(dp[root][0], dp[root][1]) << endl;

    return 0;
}

👨‍🏫 教练划重点（易错点解析）

1. 建图方向反了：

   • 题目输入是 L K（$K$ 是 $L$ 的上司）。
   • 在树形DP中，我们需要从父亲遍历到儿子，所以邻接表应该存 adj[K].push_back(L)。如果你存反了，DFS 就跑不通了。

2. 忘记找根节点：

   • 很多人习惯性地以为 1 号点就是根，但这题不一定。
   • 必须用 has_boss 数组标记，没被标记的那个才是 root。

3. 负数权值：

   • 题目说 $r_i$ 可以是负数（$-128$）。
   • 代码逻辑中 dp[u][1] = r[u] 已经处理了这种情况。如果一个人快乐值是负数，且让他去带来的负面影响超过了收益，外层的 max 会自动选择让他“不去”。

4. 初始化：

   • 进入 DFS 第一件事是清空或初始化当前点的 DP 值。虽然全局变量默认是 0，但显式写出 dp[u][0]=0 是个好习惯，逻辑更清晰。

祝你 AC！理解了这道题，树形 DP 的大门就为你打开了。

你好！我是你的OI教练。很高兴你已经开始挑战P1352，这道题在树形DP中的地位，就相当于“Hello World”之于编程语言，或者“0/1背包”之于线性DP。它是绝对的板子题。

只要彻底弄懂这道题，以后遇到“树上选点”、“最大独立集”之类的问题，你都能秒杀。

我们要把这道题拆解开，先不要急着写代码，拿出草稿纸和笔。

第一部分：思路提示

1. 状态的定义（核心中的核心） 对于树上的每一个职员（节点 $u$），他只有两种选择：去 或者 不去。 既然只有两种状态，我们不妨用二维数组来记录：

• $dp[u][0]$：表示 $u$ 不参加 舞会时，以 $u$ 为根的子树能获得的最大快乐值。
• $dp[u][1]$：表示 $u$ 参加 舞会时，以 $u$ 为根的子树能获得的最大快乐值。

2. 状态转移（怎么算？） 假设 $u$ 是上司，$v$ 是他的直系下属（子节点）。我们在递归回归（回溯）的时候，已经算好了 $v$ 的两个状态 $dp[v][0]$ 和 $dp[v][1]$。现在要算 $u$：

• 情况一：上司 $u$ 去了 ($dp[u][1]$)

  • 题目规定：如果上司去了，直系下属 $v$ 绝对不能去。
  • 所以，$u$ 的快乐值 = 自己的快乐值 + 所有下属都不去的快乐值总和。

• 情况二：上司 $u$ 没去 ($dp[u][0]$)

  • 题目规定：如果上司没去，直系下属 $v$ 去不去都可以。
  • 既然我们可以替下属做决定，为了让总快乐值最大，对于每个下属 $v$，我们当然是选“去”和“不去”里较大的那个。
  • 所以，$u$ 的快乐值 = 0 + 所有下属（$\max(\text{下属去}, \text{下属不去})$）的总和。

3. 根节点在哪里？ 题目输入给的是 l k ($k$ 是 $l$ 的上司)。但是并没有直接告诉你全公司的“大Boss”（整棵树的根）是谁。 你需要自己找出来。

• 提示：大Boss有什么特征？（他没有上司）。

第二部分：预备知识点总结

要通过这道题，你需要掌握：

1. 链式前向星 或 vector 存图：因为是树，用邻接表存储 $u$ 的所有子节点 $v$。
2. DFS（深度优先搜索）：
   • 树形DP通常采用后序遍历的思想。
   • 先递归处理子节点（算好子节点的 $dp$ 值）。
   • 回溯时再利用子节点的值更新当前节点。
3. 找根节点：使用一个 bool has_boss[N] 数组，输入时标记。最后从 1 到 $n$ 扫一遍，没被标记的就是根。
4. 基本的DP状态转移：理解 sum 和 max 的运用。

第三部分：启发式教学 —— 草稿纸上的推理

来，我们在草稿纸上把样例画出来，模拟一遍电脑的计算过程。

样例数据图示： 根据输入 1 3, 2 3, 6 4, 7 4, 4 5, 3 5，我们可以画出这就职员结构图： （注意：样例中所有人的快乐值都是 $1$）

        5 (大Boss)
       / \
      3   4 (中层领导)
     / \ / \
    1  2 6  7 (基层员工)

模拟计算流程（DFS回溯过程）：

我们从根节点 5 开始 DFS，一直钻到最底下，然后一层层往回算。

第一步：处理叶子节点 (1, 2, 6, 7) 这些是基层员工，没有下属。

• 员工 1：
  • $dp[1][0]$ (不去)：快乐值为 0。
  • $dp[1][1]$ (去)：快乐值为 $r_1 = 1$。
• 同理，员工 2、6、7 的 $dp$ 值都是：不去=0，去=1。

第二步：回溯到中层 (3, 4)

• 领导 3 (下属是 1, 2)：

  • 算 $dp[3][1]$ (3去)：下属 1 和 2 必须不去。
    • $= r_3 + dp[1][0] + dp[2][0] = 1 + 0 + 0 = 1$。
  • 算 $dp[3][0]$ (3不去)：下属 1 和 2 随便。
    • 对于下属 1：$\max(dp[1][0], dp[1][1]) = \max(0, 1) = 1$。
    • 对于下属 2：$\max(dp[2][0], dp[2][1]) = \max(0, 1) = 1$。
    • 总和 $= 0 + 1 + 1 = 2$。
  • 草稿纸记录：3号节点的状态是 (不去:2, 去:1)

• 领导 4 (下属是 6, 7)：

  • 算 $dp[4][1]$ (4去)：下属必须不去。$= 1 + 0 + 0 = 1$。
  • 算 $dp[4][0]$ (4不去)：下属取最大。$= 0 + \max(0,1) + \max(0,1) = 2$。
  • 草稿纸记录：4号节点的状态是 (不去:2, 去:1)

第三步：回溯到大Boss (5)

• Boss 5 (下属是 3, 4)：
  • 算 $dp[5][1]$ (5去)：下属 3 和 4 必须不去。
    • 我们要看 $dp[3][0]$ 和 $dp[4][0]$。
    • $= r_5 + dp[3][0] + dp[4][0]$
    • $= 1 + 2 + 2 = 5$。
  • 算 $dp[5][0]$ (5不去)：下属 3 和 4 随便。
    • 对于下属 3：我们要 $\max(dp[3][0], dp[3][1]) = \max(2, 1) = 2$。
    • 对于下属 4：我们要 $\max(dp[4][0], dp[4][1]) = \max(2, 1) = 2$。
    • 总和 $= 0 + 2 + 2 = 4$。

第四步：得出结论 最终答案就是在根节点 5 的两种状态中选最大的： $\max(dp[5][1], dp[5][0]) = \max(5, 4) = 5$。

代码逻辑框架（填空题）：

vector<int> adj[N]; // 存图
int r[N];           // 快乐值
int dp[N][2];       // DP数组
bool has_boss[N];   // 用来找根

void dfs(int u) {
    // 初始化当前节点 u 的 DP 值
    dp[u][0] = 0;
    dp[u][1] = r[u];

    // 遍历所有子节点 v
    for (int v : adj[u]) {
        dfs(v); // 先把子节点算好

        // 状态转移方程
        // 1. 如果 u 去了，v 只能...
        dp[u][1] += ...; 
        
        // 2. 如果 u 没去，v 可以...
        dp[u][0] += max(..., ...);
    }
}

int main() {
    // 1. 读入 n
    // 2. 读入 r[i]
    // 3. 读入关系，建图 (注意是 l, k，即 k -> l)，并标记 has_boss[l] = true
    // 4. 找到根节点 root (has_boss 为 false 的点)
    // 5. dfs(root)
    // 6. 输出 max(dp[root][0], dp[root][1])
}

快去尝试把代码补全吧！这是树形DP最重要的一步。

旧版题解

C++ :

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
bool b[6001];
int a[6001];
int ne;//总结点 
int f[6001][2];//寻根 
int hd[6001];
struct jiegouti{
	int v;
	int next;
};
struct jiegouti e[6001];
void so(int v,int u)
{
	ne++;
	e[ne].v=v;
	e[ne].next=hd[u];
	hd[u]=ne;
}
void dp(int u)
{
	f[u][1]=a[u];//1是要，0是不要 
	f[u][0]=0;
	for(int i=hd[u];i!=0;i=e[i].next)
	{
		int v=e[i].v;
		dp(v);
		f[u][1]+=f[v][0];
		f[u][0]=f[u][0]+max(f[v][1],f[v][0]);
	} 
	
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int l,k;
	while(cin>>l>>k&&l!=0&&k!=0)
	{
		b[l]=1;
		so(l,k);
	}
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0)
		{
			dp(i);
			cout<<max(f[i][0],f[i][1]);
			break;
		}
	}
	return 0;
}

Pascal :

program dinner;
type link=^node;
     node=record
          s:longint;
          next:link;
     end;
var r:array[1..6000]of longint;
    sum:array[1..6000,0..1]of longint;
    son:array[1..6000]of link;
    n,root:longint;
function maxnum(a,b:longint):longint;
begin
  if a>b then maxnum:=a
  else maxnum:=b;
end;{maxnum}
procedure init;
var a,b,i:longint;
    p:link;
begin
  readln(n);
  for i:=1 to n do
    begin
      readln(r[i]);
    end;{for-i}
  readln(a,b);
  while (a<>0)and(b<>0) do
    begin
      inc(root,a);
      new(p);
      p^.s:=a;
      p^.next:=son[b];
      son[b]:=p;
      readln(a,b);
    end;{while}
  root:=(n*(n+1)div 2)-root;
end;{init}
procedure calc(k:longint);
var p:link;
    i:longint;
begin
  sum[k,0]:=0;
  sum[k,1]:=0;
  p:=son[k];
  while p<>nil do
    begin
      i:=p^.s;
      calc(i);
      inc(sum[k,0],maxnum(sum[i,0],sum[i,1]));
      inc(sum[k,1],sum[i,0]);
      p:=p^.next;
    end;{while}
  inc(sum[k,1],r[k]);
end;{calc}
procedure output;
begin
  writeln(maxnum(sum[root,0],sum[root,1]));
end;{out}
begin{main}
  init;
  calc(root);
  output;
end.