头部背景图片
Decaku 's Blog |
Decaku 's Blog |

Hdu1520 Anniversary party

描述:

从树上选择一些结点,使被选择的结点的权值和最大,儿子与父亲结点最多选一个。


思路:

$设dp[0][i],表示以i为根节点,且i结点不选能取得的最大值, \\
dp[1][i]表示以i为根节点且i结点选择的最大值,答案为 \\
max\{dp[0][1],dp[1][1]\}。 \\
转移方程是 dp[0][u]=dp[0][u]+max\{dp[1][v],dp[0][v]\}; \\
dp[1][u]+=dp[0][v]; 其中v是u的儿子。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int maxn=6000+10;
int head[maxn],cnt,value[maxn];
int dp[2][maxn];

struct Edge
{
int to,nex;
} edge[maxn*2];
void add_edge(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].nex=head[u];
head[u]=cnt;
}

void dfs(int u,int f)
{
for(int i=head[u]; i!=-1; i=edge[i].nex)
{
int v=edge[i].to;
if(v==f) continue;
dfs(v,u);
dp[0][u]=dp[0][u]+max(dp[1][v],dp[0][v]);
dp[1][u]+=dp[0][v];
}
}

int main()
{
int n;
while(~scanf("%d",&n))
{
memset(head,-1,sizeof(head));
cnt=-1;
for(int i=1; i<=n; i++)
scanf("%d",&value[i]);
int u,v;
while(~scanf("%d %d",&u,&v))
{
if(!u&&!v) break;
add_edge(u,v);
add_edge(v,u);
}
memset(dp[0],0,sizeof(dp[0]));
for(int i=1; i<=n; i++)
dp[1][i]=value[i];
dfs(1,0);
printf("%d\n",max(dp[0][1],dp[1][1]));
}
}
avatar Decaku 菜菜菜