题目
点这里看题目。
分析
数据特殊，显然需要数据分治。
max{c} ≤ 1
此时 (c=0) 的点没有贡献，那么就相当于 (c) 全部相等。这样 (c) 最终的贡献与 (d) 无关，我们把 (c=1) 的点全部模拟点亮一遍即可。
max{c} > 1
不难想到做树形 DP 。我们可以想到这样的状态：
(f(u,0/1,0/1))：第一个 (0/1) 表示 (u) 是否被激发，第二个表示 (u) 的父亲是否被激发，在这个情况下将 (u) 子树内的点全部激发的最小代价。
然后你发现这样做复杂度不对无法处理儿子之间的转移顺序，或者说，我们无法有序确定哪些儿子在当前点之后被激发。其实可以，直接枚举全排列。
但注意到，如果一个儿子 (v) 在 (u) 之前激发，那么 (v) 就会给 (u) 以 (C_v) 的贡献；如果 (v) 在之后，那么 (u) 就会给 (v) 以 (C_u) 的贡献。既然一个儿子最多只有两种状态，我们就可以考虑 0/1 背包 。
考虑状态 (f(u,0/1))：表示 (u) 的父亲是否激发，此情况下 (u) 子树内全部激发的最小代价。
那么中途可以用背包进行转移， (g(i)) 表示考虑完一些儿子之后，当前点接受的能量为 (i) 的最小代价。转移显然：
[g(i)=min{g'(i-C_v)+f(v,0),g'(i)+f(v,1)}
]
最后 (f(u,0/1)) 都可以用 (g) 算出来。
注意到 (c) 很小，于是复杂度就是 (O(cn^2)) 。
小结：
- 利用 0/1 背包处理只含两种情况的转移顺序的方法，具有借鉴意义。
代码
#include <cstdio>
#include <cstring>
const int MAXN = 1e5 + 5, MAXS = 1e4 + 5;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
struct Edge
{
int to, nxt;
}Graph[MAXN << 1];
int head[MAXN], D[MAXN], C[MAXN];
int N, cnt;
void AddEdge( const int from, const int to )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
head[from] = cnt;
}
namespace AllOne
{
bool Chk()
{
for( int i = 1 ; i <= N ; i ++ )
if( C[i] > 1 ) return false;
return true;
}
void Solve()
{
int ans = 0;
for( int i = 1 ; i <= N ; i ++ )
if( C[i] == 1 )
{
ans += D[i], D[i] = 0;
for( int k = head[i] ; k ; k = Graph[k].nxt )
D[Graph[k].to] --;
}
for( int i = 1 ; i <= N ; i ++ ) ans += MAX( D[i], 0 );
write( ans ), putchar( '
' );
}
}
namespace Trivial
{
int f[MAXN][2];
int su = 0;
void DFS( const int u, const int fa )
{
int dp[MAXS]; memset( dp, 0x3f, sizeof dp );
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( ( v = Graph[i].to ) ^ fa )
DFS( v, u );
dp[0] = 0;
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( ( v = Graph[i].to ) ^ fa )
for( int j = su ; ~ j ; j -- )
if( j >= C[v] ) dp[j] = MIN( dp[j] + f[v][1], dp[j - C[v]] + f[v][0] );
else dp[j] += f[v][1];
for( int i = 0 ; i <= su ; i ++ )
f[u][0] = MIN( f[u][0], dp[i] + MAX( 0, D[u] - i ) ),
f[u][1] = MIN( f[u][1], dp[i] + MAX( 0, D[u] - i - C[fa] ) );
}
void Solve()
{
memset( f, 0x3f, sizeof f );
su = N * 5, DFS( 1, 0 );
write( f[1][0] ), putchar( '
' );
}
}
int main()
{
read( N );
for( int i = 1 ; i <= N ; i ++ ) read( D[i] );
for( int i = 1 ; i <= N ; i ++ ) read( C[i] );
for( int i = 1, a, b ; i < N ; i ++ )
read( a ), read( b ), AddEdge( a, b ), AddEdge( b, a );
if( AllOne :: Chk() ) return AllOne :: Solve(), 0;
Trivial :: Solve();
return 0;
}