题目描述
Kickstartia小镇由 V 个村庄(标记为 1 到 V)组成,由 V−1 条双向道路(标记为 1 到 V−1)连接。
其中,第 i 条路将 Xi 村与 Yi 村连接起来。
每条道路恰好连接两个村庄,没有两条道路连接同一对村庄。
此外,在Kickstartia上,任意两个村庄之间都恰好只有一条路径将它们连通。
每个村庄都有一个美丽值,第 i 个村庄的美丽值为 Bi。
请注意,村庄的美丽值可能为负数!
你将在一些村庄建造灯塔。
如果村庄中建有灯塔,或者与该村庄直接通过一条道路相连的临近村庄设有灯塔,则该村庄将被照亮。
你可以根据需要建造任意数量的灯塔(甚至为零)。
请问,你可以获得的被照亮村庄的美丽值的最大可能总和是多少?
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 V,表示村庄数量。
第二行包含 V 个整数,其中第 i 个整数是 Bi,表示第 i 个村庄的美丽值。
接下来V−1行,每行包含两个不同的整数 Xi 和 Yi,表示两个村庄之间存在一条道路。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为可以获得的被照亮村庄的美丽值的最大和。
数据范围
1≤T≤100,
−105≤Bi≤105,
1≤Xi,Yi≤V,
2≤V≤105
样例
3
9
-10 4 -10 8 20 30 -2 -3 7
1 4
2 4
4 3
9 4
9 8
7 5
6 7
7 9
4
-2 20 20 20
1 2
1 3
1 4
5
-5 -10 8 -7 -2
5 4
4 3
3 2
2 1
Case #1: 67
Case #2: 58
Case #3: 0
算法1
(树形dp) $O(n)$
dp[ i ][ j ][ k ] 表示以结点i为顶点的树,其父节点状态为j,自身状态为k时的最大值
1.dp[ i ][ 1 ][ 1 ] 表示以结点i为顶点的树,其父节点建有灯塔,其自身建有灯塔时的最大值
2.dp[ i ][ 0 ][ 1 ] 表示以结点i为顶点的树,其父节点没有建灯塔,其自身建有灯塔时的最大值
上述两种情况 B[ i ] + sum( max( dp[ k ][ 1 ][ 0 ], dp[ k ][ 1 ][ 1 ] ) );
3.dp[ i ][ 1 ][ 0 ]
B[ i ] + sum( max( dp[ k ][ 0 ][ 1 ], dp[ k ][ 1 ][ 1 ] ) );
4.dp[ i ][ 0 ][ 0 ]
都没有建有灯塔时,两种情况,
a.子结点都没有建灯塔
sum( dp[ k ][ 0 ][ 0 ] )
b.子结点至少有一个建有灯塔
设dpp[ i ][ j ] 表示前i个子结点建有灯塔的状态为j时的最大花费
dpp[ i ][ 0 ] 表示前i个子结点没有灯塔, 此时
dpp[ i ][ 0 ] = dp[ i - 1 ][ 0 ] + dp[ i ][ 0 ][ 0 ]
dpp[ i ][ 1 ] 表示前i个子结点至少有一个灯塔 此时
dpp[ i ][ 1 ] = max( dpp[ i - 1 ][ 0 ] + dp[ i ][ 0 ][ 1 ], dpp[ i - 1 ][ 1 ] + max( dp[ i - 1 ][ 0 ][ 0 ], dp[ i - 1 ][ 0 ][ 1 ] ) )
dp[ i ][ 0 ][ 0 ] = max( dpp[ i ][ 0 ], dpp[ i ][ 1 ] + B[ i ] )
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100010;
ll dp[ maxn ][ 2 ][ 2 ];
ll B[ maxn ], vis[ maxn ];
vector< int > Edge[ maxn ];
ll T, V, X, Y;
void dfs( int Root )
{
vis[ Root ] = 1;
dp[ Root ][ 0 ][ 1 ] = dp[ Root ][ 1 ][ 1 ] = dp[ Root ][ 1 ][ 0 ] = B[ Root ];
int sz = Edge[ Root ].size();
ll dpp[ sz + 1 ][ 2 ];
memset( dpp, 0, sizeof( dpp ) );
int cnt = 0;
int flag = 0;
for( auto x: Edge[ Root ] )
{
if( vis[ x ] ) continue;
dfs( x );
dp[ Root ][ 0 ][ 1 ] += max( dp[ x ][ 1 ][ 0 ], dp[ x ][ 1 ][ 1 ] );
dp[ Root ][ 1 ][ 1 ] += max( dp[ x ][ 1 ][ 0 ], dp[ x ][ 1 ][ 1 ] );
dp[ Root ][ 1 ][ 0 ] += max( dp[ x ][ 0 ][ 0 ], dp[ x ][ 0 ][ 1 ] );
++ cnt;
flag = 1;
dpp[ cnt ][ 0 ] = dpp[ cnt - 1 ][ 0 ] + dp[ x ][ 0 ][ 0 ];
if( cnt == 1 ) dpp[ cnt ][ 1 ] = dp[ x ][ 0 ][ 1 ];
else dpp[ cnt ][ 1 ] = max( dpp[ cnt - 1 ][ 1 ] + max( dp[ x ][ 0 ][ 1 ], dp[ x ][ 0 ][ 0 ] ), dpp[ cnt - 1 ][ 0 ] + dp[ x ][ 0 ][ 1 ] );
}
dp[ Root ][ 0 ][ 0 ] = 0;
if( flag ) dp[ Root ][ 0 ][ 0 ] = max( dpp[ cnt ][ 0 ], dpp[ cnt ][ 1 ] + B[ Root ] );
}
int main()
{
cin >> T;
for( int Case = 1; Case <= T; Case ++ )
{
cin >> V;
for( int i = 1; i <= V; i ++ )
{
vis[ i ] = 0;
Edge[ i ].clear();
cin >> B[ i ];
}
for( int i = 1; i <= V - 1; i ++ )
{
cin >> X >> Y;
Edge[ X ].push_back( Y );
Edge[ Y ].push_back( X );
}
dfs( 1 );
//for( int i = 1; i <= 5; i ++ ) cout << dp[ i ][ 0 ][ 0 ] << " " << dp[ i ][ 0 ][ 1 ] << " " << dp[ i ][ 1 ][ 0 ] << " " << dp[ i ][ 1 ][ 1 ] << endl;
cout << "Case #" << Case << ": " << max( dp[ 1 ][ 0 ][ 1 ], dp[ 1 ][ 0 ][ 0 ] ) << endl;
}
return 0;
}