HAOI2015树上染色

Posted on Edited on In Word count in article: 402 Reading time ≈ 1 mins.
树型Dp

[HAOI2015]树上染色

简单的说, 就是求树上所有边对答案的贡献之和

我们可以用\(Dp[i][j]\)表示以\(i\)为根的子树内, 有\(j\)个点为黑点的情况下, 这个子树中的边对答案的贡献之和

每次新加入一个\(i\)的子节点时, 另新节点中有\(k\)个黑点, 那么: \[ Dp[i][j]=max(Dp[i][j],\; Dp[i][j-k]+Dp[i_{new}]+W_{new}*Times);\\ 其中Times=子树内的黑点*子树外的黑点+子树内的白点*子树外的白点 \] 所以这道题就算是做完了

\(Dp\)一定要考虑好状态的表示, 转移和初始化

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 2e3 + 5;
int N, K, U, V, W, Size[Maxn];
int Head[Maxn], E[Maxn << 1], Cost[Maxn << 1], Next[Maxn << 1], Cur;
ll Dp[Maxn][Maxn];

inline void AddEdge(int U, int V, int W)
{
    Next[++Cur] = Head[U];
    Head[U] = Cur;
    E[Cur] = V;
    Cost[Cur] = W;
}

void DFS(int U, int _F)
{
    Size[U] = 1;
    Dp[U][0] = Dp[U][1] = 0;
    for (int i = Head[U]; i; i = Next[i])
    {
        int V = E[i];
        if (V == _F) continue;
        DFS(V, U);
        Size[U] += Size[V];
        int W = Cost[i];
        for (int i = min(K, Size[U]); i >= 0; --i)
            for (int j = 0; j <= min(i, Size[V]); ++j)
            {
                if (Dp[U][i - j] == -1) continue;//不成立的直接跳过
                ll Val = W * ((ll)j * (K - j) + (ll)(Size[V] - j) * (N - K + j - Size[V]));
                Dp[U][i] = max(Dp[U][i], Dp[U][i - j] + Dp[V][j] + Val);
            }
    }
}

int main()
{
    memset(Dp, -1, sizeof Dp);//初始化, 因为有些状态是不会成立的
    scanf ("%d %d", &N, &K);
    for (int i = 1; i < N; ++i)
    {
        scanf ("%d %d %d", &U, &V, &W);
        AddEdge (U, V, W), AddEdge(V, U, W);
    }
    DFS (1, 0);
    printf ("%lld\n", Dp[1][K]);
    system ("pause");
}