[ural 1039] Anniversary Party

Background

The president of the Ural State University is going to make an 80'th Anniversary party. The university has a hierarchical structure of employees; that is, the supervisor relation forms a tree rooted at the president. Employees are numbered by integer numbers in a range from 1 to N, The personnel office has ranked each employee with a conviviality rating. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.

Problem

Your task is to make up a guest list with the maximal conviviality rating of the guests.

Solution

一开始想的是设dp[i,j]表示以i为根的子树保留j个点所能获得的最大欢乐值

但后来发现,这样的状态转移是n^{3},那就要想重新设状态

我们观察到,一个点的欢乐值只会存在2种情况,这个点选或者不选。

所以我们设dp[i,0/1]表示这个点选还是不选的最大值

dp[i,0]=\sum max\begin{Bmatrix}dp[son[i],1],dp[son[i],0]\end{Bmatrix}

dp[i,1]=\sum dp[son[i],0]

时间复杂度O(n)

 

发表评论