"蔚来杯"2022牛客暑期多校训练营10 You are given a tree...

原题题面：https://ac.nowcoder.com/acm/contest/33195/K

题目大意：给定包含$n(1\le n\le 5000)n(\; 1\; \le \; n\; \le \; 5000\; )$个点的树$T=(V,E)T=(V,E)$,节点$ii$有权值$a_{i}a\_i$,每条边也具有一定的边权值.

求子集S ⊆ V，满足最多有$k(2\le k\le 5)k(2\backslash le\; k\backslash le5)$个点具有不同的权值，且最大化“生成边”的权值和。边$ee$是生成边，当且仅当存在$u,v\in Su,v\backslash in\; S$,边$ee$在$u,vu,v$的简单路径上。

输出最大的“生成边”的权值和。

分析：

此题的突破口在于$(2\le k\le 5)(2\backslash le\; k\backslash le\; 5)$，十分小

实际上我们可以采用$\mathrm{树}\mathrm{形}DP+\mathrm{状}\mathrm{压}DP树形DP+状压DP$的方法来解决

设$dp[u][v]dp[u][v]$表示在$uu$的子树内，方案在二进制下的表示为V的最大生成边的权值和

若点权在$11$到$kk$的范围内，对于每一个$uu$的儿子$so{n}_{i}son\_i$

有$dp[u][v]=max(dp[u][v],dp[so{n}_i][s]+dp[u][v-s]+w[so{n}_i])dp[u][v]=max(dp[u][v],dp[son\_i][s]+dp[u][v-s]+w[son\_i])$ $s\in vs\backslash in\; v$

可以以上我们仅考虑了点权在$11$到$kk$范围内时的状态，实际上点权的范围在1到$nn$之间,而空间和时间都远远不够

故可以采用随机数来优化

令点权在 [1,k] 的范围内

随机次数为200，便可得出答案（正确率高于95%）

代码：

#include<bits/stdc++.h>
#define LL long long

using namespace std;


const int MXN=5005;
struct Egde{
	int v,val,nxt;
}e[MXN*2];

int n,k,cnt;
int head[MXN],a[MXN],col[MXN];
LL ans,dp[MXN][(1<<6)];

void add(int v,int u,int w){
	e[++cnt].v=v;
	e[cnt].val=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

void dfs(int u,int fa){
	int v,w;
	for(int S=0;S<(1<<k);S++) dp[u][S]=-1e17;
	dp[u][0]=0;
	dp[u][(1<<col[a[u]])]=0;
	for(int i=head[u];i;i=e[i].nxt){
		v=e[i].v; w=e[i].val;
		if(v==fa) continue;
		dfs(v,u);
		
		for(int S=1;S<(1<<k);S++) dp[v][S]+=w;
		for(int S=(1<<k)-1;S>=0;S--){
			for(int T=S;T;T=(T-1)&S){
				dp[u][S]=max(dp[u][S],dp[u][S-T]+dp[v][T]);
				if(S-T) ans=max(ans,dp[u][S-T]+dp[v][T]);
			}
		}
	}
}

int main(){
	srand((int)time(0));
	int T,u,v,w;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w); add(v,u,w);
	}
	T=200;
	while(T--){
		for(int i=1;i<=n;i++) {
			col[i]=rand()%k;
		}
		dfs(1,0); 
	}
	printf("%lld\n",ans);
}