专栏文章

题解：P14309 【MX-S8-T2】配对

sszh_AK_alldevotion
P14309题解参与者 3已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@minhwtmc
此快照首次捕获于
2025/12/02 02:41
3 个月前
此快照最后确认于
2025/12/02 02:41
3 个月前
查看原文
神仙 dp，感觉做出这题对 dp 思维训练很有帮助。
下面称 cx=0c_x=0 的点 xx 为白点，反之为黑点。
首先不考虑交换操作。那么显然，我们每次操作肯定是需要选择相邻的两个黑点，也就是说这两个黑点的路径上没有其他黑点。例如我们现在有三个黑点 x,y,zx,y,z，其中 zz 是 x,yx,y 的最近公共祖先，然后还有一些与这三点无祖先关系的黑点。不论我们选择 x,zx,z 匹配，然后 yy 与外面的点匹配（那么我们先把 yy 到 zz 的路径加上，然后就可以把 yy 看成 zz）；还是选择 y,zy,z 匹配，然后 xx 与外面的点匹配（那么我们先把 xx 到 zz 的路径加上，然后就可以把 xx 看成 zz），贡献都是一样的，都是 xx 到 zz 的路径加上 yy 到 zz 的路径，并且剩下的点一定是 zz。其实若 zz 为白点也可以沿用这个思路，此时我们直接把 x,yx,y 匹配掉即可，若只剩下一个点未匹配，那么还是把它到 zz 的路径算上去，然后把它看成是 zz。
这样可以归纳出来，我们优先把同一棵子树内剩余的黑点匹配掉，然后若有剩余则剩下的一定是这棵子树的根。
那么考虑怎么算答案。可以记录每个子树最终剩下的点（也可能不剩下），容易发现剩下的点的个数最多为 11。然后再对当前点考虑如何匹配它每个儿子子树剩下的点即可。于是可以写出 ∑c\sum c 为偶数的暴力代码：
CodeCPP
void dfs(int x, int fa) {
	int son = 0, zui = 0;
	f[x] = liu[x] = 0;
	for (int i = 0; i < (int)g[x].size(); i++) {
		int y = g[x][i], ww = w[x][i];
		if (y == fa)
			continue;
		dis[y] = dis[x] + ww;
		dfs(y, x);
		f[x] += f[y];
		if (liu[y])
			f[x] += dis[liu[y]] - dis[x], son++;
	}
	if (son % 2 == 0 && c[x] == 1)
		liu[x] = x;
	else if (son % 2 == 1 && c[x] == 0)
		liu[x] = x;
}
∑c\sum c 为奇数咋办，可以再记一下我们是否翻转一个黑点。
CodeCPP
void dfs(int x, int fa) {
	int son = 0, so = 0, maxn = 0;
	f[x][1] = f[x][0] = liu[x][1] = liu[x][0] = 0;
	for (int i = 0; i < (int)g[x].size(); i++) {
		int y = g[x][i], ww = w[x][i];
		if (y == fa)
			continue;
		dis[y] = dis[x] + ww;
		dfs(y, x);
		f[x][0] += f[y][0];
		maxn = max(maxn, dis[liu[y][0]] - dis[x]);
		if (liu[y][0])
			f[x][0] += dis[liu[y][0]] - dis[x], son++;
		f[x][1] += f[y][0];
		if (liu[y][0])
			f[x][1] += dis[liu[y][0]] - dis[x], so++;
	}
	if (son % 2 == 0 && c[x] == 1)
		liu[x][0] = x;
	else if (son % 2 == 1 && c[x] == 0)
		liu[x][0] = x;
	int xuan = 0, mi = 1e18, kk = f[x][1];
	mi = kk - maxn;
	for (int i = 0; i < (int)g[x].size(); i++) {
		int y = g[x][i], ww = w[x][i];
		if (y == fa)
			continue;
		int z = f[y][1] - f[y][0];
		if (liu[y][1])
			z += dis[liu[y][1]] - dis[x];
		if (liu[y][0])
			z -= dis[liu[y][0]] - dis[x];
		if (kk + z < mi) {
			mi = kk + z;
			xuan = y;
		}
	}
	f[x][1] = mi;
	so++;
	if (so % 2 == 0 && c[x] == 1)
		liu[x][1] = x;
	else if (so % 2 == 1 && c[x] == 0)
		liu[x][1] = x;
}
而如上做法需要我们暴力枚举交换哪两个点，可能可以再记录一下有没有翻转黑点/有没有翻转白点，但是写起来相当复杂。
既然 ∑c\sum c 为奇数时我们需要记录是否翻转一个黑点，无论 ∑c\sum c 为奇数还是偶数我们需要记录是否翻转一个黑点，是否翻转一个白点，那不妨把黑点的状态合并起来。也就是记录我们翻转了几次黑点，翻转了几次白点，显然黑点最多翻转 22 次，白点最多翻转 11 次，那么我们实际上也无需记录最后剩下的点是谁，因为我们只看这棵子树有没有剩下点，如果剩下了那就一定是子树的根，而有没有剩下点取决于子树内黑点数量的奇偶性。
所以设 fx,i,jf_{x,i,j} 表示以 xx 为根的子树内翻转了 ii 次黑点，jj 次白点，枚举以每个儿子为根的子树内翻转了几次黑点，几次白点，背包转移即可。
CodeCPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int c[N];
vector<int>g[N], w[N];
int dis[N], sz[N], ss[N];
long long f[N][3][2], ff[3][2];

void dfs(int x, int fa) {
	sz[x] = 0;
	ss[x] = 1;
	if (c[x])
		sz[x] = 1;
	for (int i = 0; i <= 2; i++)
		for (int j = 0; j <= 1; j++)
			f[x][i][j] = 0, ff[i][j] = 1e18;
	for (int i = 0; i < (int)g[x].size(); i++) {
		int y = g[x][i], ww = w[x][i];
		if (y == fa)
			continue;
		dis[y] = dis[x] + ww;
		dfs(y, x);
		sz[x] += sz[y];
		ss[x] += ss[y];
		for (int i = 0; i <= 2; i++)
			for (int j = 0; j <= 1; j++)
				for (int ii = 0; i + ii <= 2; ii++)
					for (int jj = 0; j + jj <= 1; jj++)
						if (i <= sz[x] - sz[y] && j <= ss[x] - ss[y] - (sz[x] - sz[y]) && ii <= sz[y] && jj <= ss[y] - sz[y])
							ff[i + ii][j + jj] = min(ff[i + ii][j + jj],
							                         f[x][i][j] + f[y][ii][jj] + (sz[y] + jj - ii + 100) % 2 * (dis[y] - dis[x]));
		for (int i = 0; i <= 2; i++)
			for (int j = 0; j <= 1; j++)
				f[x][i][j] = ff[i][j], ff[i][j] = 1e18;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; i++)
		cin >> c[i], sum += c[i];
	for (int i = 1; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		g[x].push_back(y);
		g[y].push_back(x);
		w[x].push_back(z);
		w[y].push_back(z);
	}
	dfs(1, 0);
	if (sum % 2 == 0)
		cout << min(f[1][0][0], f[1][1][1]);
	else
		cout << min(f[1][1][0], f[1][2][1]);
}

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...