题解：P12452 [INOI Team Selection 2021] Color Colony

· · 题解

Solution

这题咋和这场比赛的 T1 联动了。。。

如果你很会做最优结构调整，很容易得出这个结论：所有同色边形成一个连通块。

证明是显然的。如果某个颜色构成的边形成至少两个相离的连通块，那么可以将最远的一个和周围“融合”起来。

每次进行一次操作，会使“所有颜色的连通块总数”减少。经过有限步调整之后，一定会满足同色边形成一个连通块。

放一张图让大家理解一下：

比如这有两个橘色边形成的连通块。如果希望跨块产生贡献，一定会包含这条蓝色的边。那么把右边整个连通块变成蓝色的，显然不会变劣。

那么就很好树形 DP 了。设 dp_{u,i} 表示考虑了 u 的子树和 u \to fa_u 的边，满足 u 子树到 fa_u 中最长的无重复颜色的路径长度为 i，最多用多少种颜色（只考虑子树内）。

合并的时候（u 已经连了最长路径为 i_1，连接一个 i_2。如果 i_1 + i_2 > k 那么需要他们同色）。

但是你显然不能动态更新 i，比如前面的 i 很小，后面跟了一个很大的，那么你无法处理他们全部合并。不过这也不难，你可以假定最后的 i。反正你算大了“错解不劣”。

然后你要将 u \to fa_u 的边加上去。他可以选择和目前的最长路径同色，这样直接消除了最长路径的影响。也就是说，我们还得维护次长路径，表示不和最长路径合并的最长长度。

次长路径这件事情不需要在 DP 状态中体现，只是转移中有用。使用前缀和优化容易做到 O(nk^2)。

具体来说，我们记 tmp_{i,j,0/1} 表示，我们钦定最长路 \le i，和最长路不相同的路径 \le j，是否已经选了至少一条边作为最长路径。轻微卡空间。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,k,dp[MAXN][35];
vector<int> G[MAXN];
void dfs(int u,int f) {
    int tmp[35][35][2];
    memset(tmp,0,sizeof(tmp));
    int s=0;
    for(auto v:G[u]) if(v!=f) {
        dfs(v,u),++s;
        int ntmp[35][35][2];
        memset(ntmp,0,sizeof(ntmp));
        ffor(i,1,k-1) ffor(j,0,min(i,k-1-i)) ffor(o,0,1) {
            ntmp[i][j][o|1]=max(ntmp[i][j][o|1],tmp[i][j][o]+dp[v][i]-1+(!o));
            ntmp[i][j][o]=max(ntmp[i][j][o],tmp[i][j][o]+dp[v][j]);
        }
        ffor(i,0,k-1) ffor(j,0,k-1) ffor(o,0,1) tmp[i][j][o]=ntmp[i][j][o];
    }
    if(!s) dp[u][1]=1;
    else {
        if(u!=1) ffor(i,1,k-1) ffor(j,0,min(i,k-i-1)) dp[u][j+1]=max(dp[u][j+1],tmp[i][j][1]),dp[u][i+1]=max(dp[u][i+1],tmp[i][j][1]+1);
        else {
            int ans=0;
            ffor(i,1,k-1) ffor(j,0,min(i,k-i-1)) ans=max(ans,tmp[i][j][1]);
            cout<<ans;
        }
    }
    ffor(j,1,k-1) dp[u][j]=max(dp[u][j],dp[u][j-1]);
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    if(n==1) return cout<<0,0;
    ffor(i,1,n-1) {int u,v;cin>>u>>v;G[u].push_back(v),G[v].push_back(u);}
    dfs(1,0);
    return 0;
}