【HDU 1520 Anniversary party】

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1520

Problem Description

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.

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个人,每个人参加一个晚会都会有一个快乐度\(k\),如果他上司也参加那么他就不能参加,求晚会的最大快乐度。

树形DP模板题,\(dp[i][0]\)表示不选第\(i\)人的最大快乐度,\(dp[i][1]\)表示选了第\(i\)人的最大快乐度。如果不选\(i\),那么\(i\)的子节点都没有限制;如果选了\(i\),那么子节点只能不选。看网上很多模板都是单向边找根节点,其实不用那么麻烦,本质上树形DP就是在给定n个点关系的一张图上DP罢了,反正和某个人相连的肯定是他上司,选某人不选其上司同时也意味着选上司不选他,干嘛非要从上司往下属DP……所以直接建双向边从任意一点开始DP就是啦

那么显然有:

\(dp[i][0]=\sum\limits_{k=1}^{n}max(dp[son[k]][0],dp[son[k]][1])\) ,其中\(son[k]\)是与\(i\)相连的第\(k\)个节点。

\(dp[i][1]=\sum\limits_{k=1}^{n}dp[son[k]][0]\),其中\(son[k]\)是与\(i\)相连的第\(k\)个节点。

从1开始DP那最终答案就是\(max(dp[1][0],dp[1][1])\)啦~

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*