自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:15:39，当前版本为作者最后更新于2025-05-20 17:03:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}