BZOJ P4033 LOJ 2124 [HAOI 2015] 나무 염색[나무형 DP+가방]

제목 분석(이하 M M은 제목에 입력된 K K):
트리 DP D P.우리는 나무DP DP의 방법에 따라 (뭐라고? 나무DP의 방식을 몰라?)이 문제의 상태 설정은 다음과 같다.
DP[I][J]DP[I][J]는 II를 뿌리로 한 자수 중 J개의 검은 점을 칠한 최대 수익 J<=MJ<=M
그렇다면 문제는 우리가 상태 이동을 어떻게 해야 하는가이다. 관건은 상태 이동을 할 때 발생하는 수익 변화를 어떻게 처리해야 하는가이다.
다음 사항을 살펴보겠습니다.
나무의 가장자리 Edge(X, Y) E d g e(X, Y), X X 를 Y Y의 아버지 노드로 설정해도 무방하다. 우리는 X X를 뿌리로 하는 자수 밖(X X 점 포함)에 모두 PP의 검은 점이 없다고 가정하면 X X를 뿌리로 하는 자수 안, 즉 YY 안(X X 점 포함하지 않고 Y 점 포함)에 모두 M-P M - P의 검은 점이 있다.관건은 곱셈 원리에 따라 모든 검은 점이 가장자리에 연결되면 모두 P (M: P) P (M: P) 테두리가 있는데, 이 P (K: P) P (K. P) 테두리는 모두 같은 테두리를 통과한다.이렇게 하면 우리는 계산해야 할 거리를 어느 한 변의 계산으로 전환시켜 우리의 이동을 편리하게 할 수 있다.
그래서 아래의 상태 이동 방정식을 얻을 수 있다(사실은 나무에서 배낭을 메는 과정이다).
Size[X] S i z e [X]는 X X 를 루트로 하는 하위 트리의 크기를 나타냅니다.
DP[X][J]=maxDP[X][J],DP[X][J−K]+DP[Y][K]+K∗(J−K)∗(X−>Y)+(Size[Y]−K)∗(N−M−Size[Y]+K)∗(X−>Y) D P [ X ] [ J ] = m a x D P [ X ] [ J ] , D P [ X ] [ J − K ] + D P [ Y ] [ K ] + K ∗ ( J − K ) ∗ ( X − > Y ) + ( S i z e [ Y ] − K ) ∗ ( N − M − S i z e [ Y ] + K ) ∗ ( X − > Y )
이 나무에서 어느 점이 뿌리 노드인지는 상대적인 것이기 때문에 코드를 토론하고 쓰기에 편리하도록 모두 11호점을 뿌리 노드로 하기 때문에 마지막 답은 DP[1][M]DP[1][1][M]이다.
또한, 이 문제가 끊길 것 같을 때, 여러분은 불필요한 곳에서 long long l o n g l o n g
그래서 이제 코드가 잘 쓰여졌어요. 핵심 코드:

void Tree_DP(int X,int Fx){
    int I,J,K;Size[X]=1;
    for(I=Head[X];I;I=Next[I]){
        int Y=To[I];
        if(Y!=Fx){
            Tree_DP(Y,X);
            Size[X]+=Size[Y];
        }
    }
    for(I=0;I<=Size[X];I++){
        DP[X][I]=-1ll;
    }DP[X][0]=DP[X][1]=0ll;
    for(I=Head[X];I;I=Next[I]){
        int Y=To[I];LL Z=Edge[I];
        if(Y!=Fx){
            int NumX=min(M,Size[X]);
            for(J=NumX;J>=0;J--){
                int NumY=min(J,Size[Y]);
                for(K=0;K<=min(NumY,J);K++){
                    if(DP[X][J-K]!=-1ll){
                        DP[X][J]=max(DP[X][J],DP[X][J-K]+DP[Y][K]+(LL)K*(M-K)*Z+(LL)(Size[Y]-K)*(N-M-Size[Y]+K)*Z);
                    }
                }
            }
        }
    }
}