专栏文章

题解：P11529 [THUPC2025 初赛] 辞甲猾扎

hhappy_zero
P11529题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miqjpyo5
此快照首次捕获于
2025/12/04 05:55
3 个月前
此快照最后确认于
2025/12/04 05:55
3 个月前
查看原文
稍微转换一下题目，由于所有灰点都不被变成黑色，所以等价于与黑色相邻的点最后都是白色（相邻都被变成后白色黑色就“扩散”不出去了），也就是其要么本身为白色，要么其还和一个白点相邻。
原图是一棵树，考虑树形 dp。稍微分讨一下可以得出一下定义：
  • fi,0f_{i,0} 表示 ii 是灰点，不需要与白色相邻，其子树内最少要染白的个数
  • fi,1f_{i,1} 表示 ii 是灰点，需要与白色相邻且已与白色相邻，其子树内最少要染白的个数
  • fi,2f_{i,2} 表示 ii 是灰点，需要与白色相邻且未与白色相邻，其子树内最少要染白的个数
  • fi,3f_{i,3} 表示 ii 是白点，其子树内最少要染白的个数
  • fi,4f_{i,4} 表示 ii 是黑点，其子树内最少要染白的个数
设当前有 fjf_j 向 fif_i 转移（j∈sonij\in son_i），分三种情况：
  1. ii 是黑点：
    • fi,0/1/2/3=+∞f_{i,0/1/2/3}=+\infty
    • fi,4=∑min⁡(fj,1,fj,3,fj,4)f_{i,4}=\sum \min(f_{j,1},f_{j,3},f_{j,4})（fj,0f_{j,0} 不存在，fj,2f_{j,2} 的 jj 不满足条件）
  2. ii 是灰点且未与黑点相邻：
    • fi,1/2/4=+∞f_{i,1/2/4}=+\infty
    • fi,0=∑min⁡(fj,0,fj,1,fj,3)f_{i,0}=\sum \min(f_{j, 0},f_{j,1},f_{j,3})（fj,4f_{j,4} 不存在，fj,2f_{j,2} 的 jj 不满足条件）
    • fi,3=∑min⁡(fj,0,fj,1,fj,2,fj,3)f_{i,3}=\sum \min(f_{j, 0},f_{j,1},f_{j,2},f_{j,3})（除了 fj,4f_{j,4} 不存在其它随便转）
  3. ii 是灰点且与黑点相邻：
    • fi,0/4=+∞f_{i,0/4}=+\infty
    • fi,2=∑min⁡(fj,0,fj,1,fj,4)f_{i,2}=\sum \min(f_{j, 0},f_{j,1},f_{j,4})（fj,2f_{j,2} 的 jj 不满足条件，fj,3f_{j,3} 的 ii 矛盾）
    • fi,3=∑min⁡(fj,0,fj,1,fj,2,fj,3,fj,4)f_{i,3}=\sum \min(f_{j, 0},f_{j,1},f_{j,2},f_{j,3},f_{j,4})（这个真没任何限制了）
    • fi,1f_{i,1} 先对于每个子树求随便染（wj=min⁡(fj,0,fj,1,fj,3,fj,4w_j=\min(f_{j, 0},f_{j,1},f_{j,3},f_{j,4}）的方案数和，然后选其中染白代价（fj,3−wjf_{j,3}-w_j）最小的一个换成 fj,3f_{j,3}
答案即为 min⁡(frt,0,frt,1,frt,3,frt,4)\min(f_{rt, 0}, f_{rt, 1}, f_{rt, 3}, f_{rt, 4})。
感觉做得有些复杂了，不过状态定义清楚了就很好做了 （但不好说是谁想状态想了 2h 吃了三发罚时）。所以为什么这题过得比 I 和 D 还多啊。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
const int INF = 1e9;
bool vis[N], f1[N];
int f[N][5];
vector <int> p[N];
void dfs(int k, int fa) {
	f[k][3] = 1; 
	for (auto i : p[k])
		if (i != fa) dfs(i, k);
	if (vis[k]) {
		f[k][0] = f[k][1] = f[k][2] = f[k][3] = INF;
		for (auto i : p[k])
			if (i != fa)
				f[k][4] += min({f[i][1], f[i][3], f[i][4]});
	} else if (!f1[k]) {
		f[k][1] = f[k][2] = f[k][4] = INF; 
		for (auto i : p[k]) {
			if (i == fa) continue;
			f[k][0] += min({f[i][0], f[i][1], f[i][3]});
			f[k][3] += min({f[i][0], f[i][1], f[i][2], f[i][3]}); 
		}
	} else {
		f[k][0] = f[k][4] = INF; int t = INF; 
		for (auto i : p[k]) {
			if (i == fa) continue;
			f[k][2] += min({f[i][0], f[i][1], f[i][4]});
			f[k][3] += min({f[i][0], f[i][1], f[i][2], f[i][3], f[i][4]});
			int w = min({f[i][0], f[i][1], f[i][3], f[i][4]});
			if (!vis[i]) t = min(t, f[i][3] - w); f[k][1] += w; 
		}
		f[k][1] += t; 
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, k; cin >> n >> k;
	for (int i = 1, x; i <= k; i++) 
		cin >> x, vis[x] = true;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		p[u].push_back(v);
		p[v].push_back(u); 
		f1[u] |= vis[v], f1[v] |= vis[u];
	}
	dfs(1, 0); cout << min({f[1][0], f[1][1], f[1][3], f[1][4]});
	return 0;
}

评论

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

正在加载评论...