dp[i][0] 表示不选第i个节点的最大价值,dp[i][1]表示选第i个节点获得的最大价值。
状态转移方程:
dp[i][1] = val[i] + E dp[j][0] ( j是i的子节点 E表示求和 );
dp[i][0] = E max(dp[j][0], dp[j][1] )(j是i的子节点);
对于叶子节点有:
dp[i][0] = 0;
dp[i][1] = val[i];
有不清楚的画下图就知道了。
AC代码如下:
#include <iostream> #include <vector> #include <cstdio> using namespace std; int N; vector<int> gra[6001]; int val[6001]; bool visit[6001]; int dp[6001][2]; inline int max( int a, int b ){ return ( a > b ? a : b ); } void DFS( int n, int pre ){ visit[n] = true; if( gra[n].size() == 0 && gra[n][0] == pre ){ dp[n][0] = 0; dp[n][1] = val[n]; return; } for( int i = 0; i < gra[n].size(); i++ ){ int t = gra[n][i]; if( visit[t] ){ continue; } DFS( t, n ); dp[n][1] += dp[t][0]; dp[n][0] += max( dp[t][0], dp[t][1] ); } dp[n][1] += val[n]; } int main(){ while( scanf( "%d", &N ) != EOF ){ memset( visit, false, sizeof( visit ) ); memset( dp, 0, sizeof( dp ) ); for( int i = 0; i < 6001; i++ ){ gra[i].clear(); } for( int i = 1; i <= N; i++ ){ cin >> val[i]; } int temp1, temp2; while( scanf( "%d%d", &temp1, &temp2 ) ){ if( temp1 == 0 && temp2 == 0 ){ break; } gra[temp1].push_back( temp2 ); gra[temp2].push_back( temp1 ); } DFS( 1, -1 ); cout << max( dp[1][0], dp[1][1] ) << endl;; } return 0; }