P3177 [HAOI2015] 树上染色 题解

菲斯斯夫斯基 · 2024-04-18 18:51:09 · 题解

P3177 [HAOI2015] 树上染色 题解

本题解选自我的树上 dp 小记。

好题。

一开始理所当然地想设计 dp_{x,j} 为在 x 子树内染了 j 个点的最大价值。然后想了好久都没有思路，因为还会与子树外的点产生贡献。

正确的设计方式应该是 在 x 子树内染了 j 个点对答案的贡献。这样设计的好处是转移时直接求和即可，没有其他的贡献。

设计好数组就转移就很方便了：

上面的 k 是枚举在 i 子树内选多少个黑点，v 是边的权值，s_i 是 i 子树大小，s_x 是目前枚举到的 x 子树大小。k\times (m-k) 是两边的黑点连起来经过当前这条边的次数，因为在两边任意选一个点都会经过；同理，(s_i-k)\times (n-m-s_i+k) 就是白点的。

注意转移的上下界和一些细节。原始的大部分题解都是要把 dp 数组 memset 成 -1，不然会 WA。理由是可能会从不合法的状态转移而来，但这样也同时导致了时间复杂度是错误的。

为什么会从错误的状态转移而来呢？我们枚举了 i 子树内有 k 个点，那么就要要求前面的子树内至少有 j-k 个点。原本 k 从 0 开始枚举的话就会有可能前面点的个数不够，从而导致从不合法的状态转移来。

时间复杂度的分析建议看这个帖子，这里就不过多赘述了。简单而不一定严谨地说，任意两个点只会在 lca 处合并一次，所以时间复杂度是 \mathcal O(n^2) 的。

本题的困难主要在需要打破以前只计算子树内答案的思维，直接考虑对答案的贡献，正确设计 dp 数组。

这里给出代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=2010;
int n,m,s[N];
long long dp[N][N];
vector<pair<int,int>>v[N];
void dfs(int x,int fa)
{
    s[x]=1;
    for(auto i:v[x])
    {
        if(i.fi==fa)continue;
        dfs(i.fi,x);
        s[x]+=s[i.fi];
        for(int j=max(m,s[x]);j>=0;j--)
            for(int k=max(j-s[x]+s[i.fi],0);k<=min(j,s[i.fi]);k++)//控制好上下界
                dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[i.fi][k]+1ll*k*(m-k)*i.se+1ll*(s[i.fi]-k)*(n-m-s[i.fi]+k)*i.se);
    }
}
int main()
{
    cin>>n>>m;
    m=min(m,n-m);//染黑或染白都是一样的
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    dfs(1,0);
    cout<<dp[1][m];
    return 0;
}