Anniversary party(树形dp 基础题)

1.题目大意

There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests’ conviviality ratings.
InputEmployees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form:
Input
Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
Output
Output should contain the maximal sum of guests’ ratings.
Sample Input
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
Sample Output
5

题意：有一个庆典晚会，想邀请一些人来参加。每个人都有自己的值（权值），问如果两个人之间有直接的上下级关系，那么他们中只能来一个。即如果某位员工参加了聚会，他的直接上司不能参加；但如果他没有参加，他的直接上司是否参加都没有关系。求请来的一部分人的最大欢乐值是多少。

输入：

有n个人，接下来给出的是n个人的权值，在接下来n行给出的是l，k，k是l的上司，l与k不能同时出现，求如何取能得到最大欢乐值。
首先，我们分析一下给出的输入数据：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

这个输入数据可以分为几个部分：

1. 第一行 7: 表示有7位员工。
2. 接下来的7行: 每行都是一个数字，表示每位员工的欢乐值。按顺序，员工1到员工7的欢乐值都是1。
3. 接下来的行: 这些行描述了员工之间的上下级关系。每行有两个数字，第一个数字是下属，第二个数字是他们的上司。例如，1 3 表示员工1是员工3的下属。
4. 最后一行 0 0: 这可能是一个标记行，表示输入的结束。

根据这些上下级关系，我们可以构建以下的层级结构：

      5/   \3     4/ \   / \1   2 6   7

员工5是最高级的员工，他有两个直接下属，分别是员工3和员工4。员工3有两个下属，分别是员工1和员工2。员工4也有两个下属，分别是员工6和员工7。

2.问题分析

当然可以！

这个问题可以通过树形动态规划来解决。问题中的核心思想是：如果某位员工参加了聚会，他的直接上司不能参加；但如果他没有参加，他的直接上司是否参加都没有关系。

给定这个问题，对于每位员工（即树的节点），我们需要记录两个值：
这三行代码是树形动态规划中关键的部分，它们处理了每个员工参加或不参加聚会的情况。我将为你详细解释这三行代码的工作方式。

首先，我们看一下DP的定义：

• dp[node][0]：代表员工node不参加聚会时，他及其所有下属能够带来的最大欢乐值。
• dp[node][1]：代表员工node参加聚会时，他及其所有下属能够带来的最大欢乐值。

接下来，状态转移方程

1. dp[node][0] += max(dp[child][0], dp[child][1]);
   这行代码处理的是员工node不参加聚会的情况。由于node不参加，他的每一个下属child都可以选择参加或不参加。我们选择让下属child处于能够带来更大欢乐值的状态。因此，我们取dp[child][0]和dp[child][1]的较大值，累加到dp[node][0]中。

2. dp[node][1] += dp[child][0];
   这行代码处理的是员工node参加聚会的情况。由于上司不能与其直接下属同时参加聚会，所以当node参加聚会时，他的所有下属child都不能参加。这就意味着我们只累加dp[child][0]（即child不参加时的欢乐值）到dp[node][1]中。

总结一下，这两行代码为每个员工计算了两种情况的最大欢乐值：员工自己参加聚会和不参加聚会。这两种情况都考虑了其所有下属可能带来的欢乐值。

3.问题解决代码

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;const int MAXN = 6005;vector<int> tree[MAXN];
int ratings[MAXN];
int dp[MAXN][2];
int father[MAXN];void dfs(int node) {dp[node][0] = 0;dp[node][1] = ratings[node];for(int child : tree[node]) {dfs(child);dp[node][0