나무형 의존 가방

문제 의 대의: 나무 한 그루 를 주 고 뿌리 노드 는 1 이 며 점 마다 독소 와 수확 이 있다.독소 가 주어진 값 을 초과 하지 않 을 경우 수확 이 가장 크다.한 점 의 아버지 노드 가 선택 되 어야 이 점 이 선택 된다.
먼저 dfs 순 서 를 만 들 고 모든 점 의 하위 나무 와 자신의 크기 를 기록 합 니 다.모든 점 이 선택 되 거나 선택 되 지 않 을 수 있 으 며, 선택 되 어야 나무 가 고려 된다.f [i] [j] 를 설정 하면 dfs 순서 에서 i 위 에 있 는 점 이 서브 트 리 와 자신 에 게 독소 와 j 의 점 을 선택 하여 얻 을 수 있 는 최대 수익 을 나타 낸다.(아래 x 는 dfs 순서 에서 i 번 째 대표 점 을 가리킨다)
만약 j < cost [x], f [i] [j] = f [i + size [x] [j].이 점 과 그 서브 트 리 를 선택 할 수 없습니다 (+ size [x] 는 dfs 순서 에서 이 점 을 뛰 어 넘 는 서브 트 리 를 대표 합 니 다) 만약 j ≥ cost [x], f [i] [j] = max (f [i + 1] [j - c [x]] + v [x], f [i + size [x] [j]).마이너스 수익 이 발생 할 지 주의 하고 0 과 비교 해 야 할 지 여 부 를 선택 하 세 요.

#include 
#include 
#include 
#include 
using namespace std ;
bool Read ( int &x, char c = getchar(), bool flag = false ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) if ( c == EOF ) return false ; else if ( c == '-' ) flag = true ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ; if ( flag ) x = -x ;
    return true ;
}
const int maxn = 5010, maxm = maxn<<1, zhf = 1<<28 ;
int ans, n, m, e, be[maxn], to[maxm], nxt[maxm], v[maxn], c[maxn], dfn[maxn], rdn[maxn], clk, size[maxn], f[maxn][maxn] ;
void add ( int x, int y ) {
    to[++e] = y ;
    nxt[e] = be[x] ;
    be[x] = e ;
}
void dfs ( int x, int fa ) {
    ( dfn[x] = ++clk )[rdn] = x ;
    size[x] = 1 ;
    int i, u ;
    for ( i = be[x] ; i ; i = nxt[i] ) {
        u = to[i] ;
        if ( u == fa ) continue ;
        dfs(u,x) ;
        size[x] += size[u] ;
    }
}
int main() {
    int i, j, k, x, y, z ;
    Read(n) ; Read(m) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(v[i]) ;
        Read(c[i]) ;
    }
    for ( i = 1 ; i < n ; i ++ ) {
        Read(x) ; Read(y) ;
        add ( x, y ) ;
        add ( y, x ) ;
    }
    dfs(1,1) ;
    for ( i = n ; i ; i -- ) {
        x = rdn[i] ;
        for ( j = 0 ; j <= m ; j ++ )
            if ( j < c[x] ) f[i][j] = max ( f[i+size[x]][j], 0 ) ;
            else f[i][j] = max ( max( f[i+1][j-c[x]]+v[x], f[i+size[x]][j] ), 0 ) ;
    }
    printf ( "%d
", f[1][m] ) ;
    return 0 ;
}

Wearry 가 모 의 경기 에서 이 지식 을 언급 해 주 셔 서 감사합니다.