F - 树上染色

Des

给定一棵树，要求在树上把 $m$ 个点染成黑色，并有价值函数

$$v(E’) = \sum_{v_1,v_2\in E’} dis(v_1,v_2) + \sum_{v_1,v_2\in E-E’} dis(v_1,v_2)$$

求一种染色方式使得最大化 $v(E’)$。

Sol

仍然考虑动态规划。

$f_{u,k}$ 表示 $u$ 子树内选择 $k$ 个 对答案的贡献。考虑这和 $f_{u,k}$ 表示 $u$ 子树内选择 $k$ 个 的价值 有什么不同。

对于答案的贡献，我们是默认在 $u$ 子树之外已经选择了 $m-k$ 个其他的黑色节点的，因此对于边 $u\to v$，若有 $v$ 子树内已经选择了 $k$ 个，那么边 $u\to v$ 经过的次数就是 $k\times(m-k)$ 次，因此对答案的贡献就是 $w\times k\times (m-k)$。同理可以计算得到白点的贡献。

而价值指的是 $u$ 子树内选择 $k$ 个，而 $v$ 子树内选择 $k’$ 个的贡献，这是不好被统计的。

由第一个设的状态，我们有转移方程：

$$f_{u,j} = \max{f_{v,k} + f_{u,j-k} + w\times k\times (m-k) + w\times (sz_v-k)\times (n-m-sz_v+k)}$$

但是这样显然会 $\text{TLE}$。这是因为我们需要 $DFS$，并且每个点枚举一个 $j$ 和一个 $k$，复杂度 $O(nk^2)$。无法接受。

我们做一个上下界优化。显然，$j$ 的上下界是 $[0,\min(m,sz_u)]$，其中 $u$ 是已经遍历到的 $u$ 子树的大小。而 $k$ 的范围是 $[\max(j-sz_u+sz_v,0),\min(sz_v,m)]$。因此，式子就变成了：

$$f_{u,j} = \max_{j=0}^{\min(m,sz_u)}\max_{k=\max(j-sz_u+sz_v,0)}^{\min(sz_v,m)}{f_{v,k} + f_{u,j-k} + w\times k\times (m-k) + w\times (sz_v-k)\times (n-m-sz_v+k)}$$

为啥复杂度是对的前几篇题解写得也已经很明确了。这里需要注意的是 $j$ 需要倒序枚举，否则答案会不正确。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>

#include<bitset>
#include<set>

#include<deque>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#include<random>

#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define DBG cerr << __LINE__ << ' ' << __FUNCTION__ << endl

#define DRE default_random_engine
#define UID uniform_int_distribution
#define y0 Y0
#define y1 Y1
#define endl '\n'

#define pi acos(-1)
#define eps (1e-8)
#define null nullptr

using namespace std;

#define int long long
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int N = 2e3 + 10;
const int M = 5e2 + 10;

int f[N][N], n, m, siz[N];
vector<PII> g[N];

void solve(int x,int fa){
	siz[x] = 1;
	for(PII y:g[x]){
		if(y.fi == fa)  continue;
		solve(y.fi, x);
		siz[x] += siz[y.fi];
		for(int j = max(siz[x], m); j>=0; --j)
			for(int k = max(j - siz[x] + siz[y.fi], 0ll); k <= min(j, siz[y.fi]); ++k)
				f[x][j] = max(f[x][j], f[y.fi][k] + f[x][j-k] + y.se * k * (m-k) + y.se * (siz[y.fi]-k) * (n-m-siz[y.fi]+k));	
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i=1,x,y,z;i<n;++i)  cin>>x>>y>>z, g[x].pb(mk(y,z)), g[y].pb(mk(x,z));
	solve(1, 0);
	cout<<f[1][m]<<endl;
	return 0;
}

树上染色 题解

F - 树上染色

Des

Sol

树上染色题解