#C241015C. 最大生成树(treemax)

标签（Label）

动态规划（状态压缩DP、树形DP）
Color Coding

网址（Website）

题目详情 - 最大生成树(treemax) - Super

题解 - 最大生成树(treemax) - Super

题解（Solution）

出题者题解

算法分析

此题的突破口在于 $(2 \leq k \leq 5)$，这个范围相对较小，为我们提供了解决问题的线索。

实际上，我们可以采用 树形 DP + 状压 DP 的方法来解决这个问题。

设 $dp[u][v]$ 表示在节点 $u$ 的子树内，当点权的选择状态在二进制下表示为 $v$ 时（其中 $v$ 的二进制位表示点权是否被选中），所能得到的最大生成边的权值和。

若点权在 $1$ 到 $k$ 的范围内，对于每一个节点 $u$ 的儿子 $son_i$，我们可以遍历所有可能的点权选择状态 $v$，并考虑将 $son_i$ 的子树中的点权选择状态 $s$（其中 $s$ 是 $v$ 的子集）与 $u$ 的其他子树中的点权选择状态 $v-s$ 进行组合。这样，我们就可以通过比较不同组合下的最大生成边权值和来更新 $dp[u][v]$。具体地，状态转移方程如下：

$dp[u][v] = \max(dp[u][v], dp[son_i][s] + dp[u][v-s] + w[son_i])$ ，其中 $s \in v$

然而，以上分析仅考虑了点权在 $1$ 到 $k$ 范围内时的状态。实际上，点权的范围在 $1$ 到 $n$ 之间，直接应用上述方法会导致空间和时间复杂度过高，无法承受。

为了解决这个问题，我们可以采用随机数优化的方法。具体来说，我们可以多次（如200次）随机地将点权映射到 $[1, k]$ 的范围内，并在每次映射后应用上述的状压DP方法。由于 $k$ 的范围较小，这样的随机映射可以大大降低空间和时间复杂度。最后，我们可以取多次随机映射后的最大生成边权值和的最大值作为最终答案。需要注意的是，由于随机化的引入，这种方法并不能保证得到绝对正确的答案，但多次随机后，它计算出错误的概率就极低了。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 4005;
bool ST;
mt19937_64 rnd(time(0));

vector<P> ft[N];
int n,k,ans,a[N],b[N];

int f[N][1<<6|3];
int col[N];

void dfs(int x,int F){
	f[x][0] = f[x][1<<(b[x]-1)] = 0;
	for(auto p:ft[x]){
		int y = p.x, v = p.y;
		if(y==F) continue;
		dfs(y,x);
		For(i,0,(1<<k)-1) f[y][i] += v;
		Rof(i,(1<<k)-1,0){
			for(int j = i; j; j = (j-1)&i){
				f[x][i] = max(f[x][i], f[x][i^j]+f[y][j]);
				if(i!=j) ans = max(ans, f[x][i^j]+f[y][j]);
			}
		} 
	}
}

void solve(){
	n = rd(), k = rd();For(i,1,n) a[i] = rd();
	For(i,1,n-1){
		int x = rd(), y = rd(), v = rd();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
	}
	int tt = 100;
	while(tt--){
		For(i,1,n) col[i] = rnd()%k+1;
		For(i,1,n) b[i] = col[a[i]];
		memset(f,-0x3f, sizeof f); 
		dfs(1,0);
	}printf("%lld\n",ans);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("treemax.in","r",stdin);
	freopen("treemax.out","w",stdout);
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}