专栏文章

题解：P12136 [蓝桥杯 2025 省 B] 生产车间

UUntitled_unrevised
P12136题解参与者 7已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@mipn4b3f
此快照首次捕获于
2025/12/03 14:42
3 个月前
此快照最后确认于
2025/12/03 14:42
3 个月前
查看原文
能意识到 G 有多难就能意识到 G 有多简单。
本文将介绍 P12136 [蓝桥杯 2025 省 B] 生产车间 与子集和问题之间的关联，并给出基于此得出的做法，以及可能的时间优化方式。

题意简述

给定一棵有根树，忽略若干个节点使得对于剩下的非叶节点 uu，它所包含的剩下的叶节点权值之和都 ≤wu\le w_u；并对于根节点 11，最大化它所包含的剩下的叶节点权值之和。

题目分析

树上问题，自然想到要用树形 dp 来做。然后注意到数据范围 n≤1,000n \le 1,000 和 w≤1,000w \le 1,000，应该能意识到这题只要求平方时间的做法。
这意味着，或许，这个题很难，使得更低复杂度的做法可能是不存在的。但到底有多难？我们可以拿另一个已经有明确难度的题来比较。

与子集和问题的联系

考虑一种比较极端的数据：除了 11 之外的所有节点全都是叶节点，编号构成的集合为 L={2,3,…,n}L = \{2, 3, \dots, n\}。此时问题转化成找出一个子集 T⊆LT \sube L 使得 ∑v∈Twv≤w1\sum_{v \in T} w_v \le w_1 且 ∑v∈Twv\sum_{v \in T} w_v 最大。
如果你解决了该问题，那么通过判定 ∑v∈Twv\sum_{v \in T} w_v 是否等于 w1w_1，你就直接判定了 LL 是否存在一子集，它的权值和为 w1w_1。而这就是著名的子集和问题，在值域没有限制的时候是 NP-Complete 的。
综上，该问题是严格不弱于子集和问题的，如果 ww 没有限制，n≤1000n \le 1000 这样大的范围是难以短时间做出来的。

小值域子集和问题

现在应该就能看出 w≤1,000w \le 1,000 的作用了。子集和问题虽然是 NP-Complete 的，但是其存在 O(n∑w)O(n\sum w) 的伪多项式时间的做法。对于本题而言，ww 是限制在每一个节点上的，从而对每一个节点，它的子集和的范围都不过 O(w)O(w) 而已。
到了这里，应该就能够得出 O(nw2)O(nw^2) 的做法了：
  • 对于每一个叶节点 uu，它有选与不选两种选择，从而所有可能的子集和为 Su={0,wu}S_u = \{0, w_u\}；
  • 对于每一个枝节点 vv，从它所有子节点可能的子集和计算出自己可能的的子集和然后除去 >wv\gt w_v 的，具体而言：
Sv=(Sr1+Sr2+⋯+Srd+(v))∩[0,wv]S_v = (S_{r_1} + S_{r_2} + \dots + S_{r_{d^+(v)}}) \cap [0, w_v]
其中 S+T={s+t∣∀s∈S,∀t∈T}S + T = \{s + t \mid \forall s \in S, \forall t \in T\}，rir_i 是 vv 的第 ii 个子节点。
最后对于 S1S_1，输出 max⁡S1\max S_1 即可。

可能的优化

尽管 O(nw2)O(nw^2) 很有可能跑不满但仍然是可达到的，一旦达到了就可能超时。由于瓶颈在子集和问题上且不可能比子集和问题简单，唯一的方法就是优化解决子集和问题的算法。
可以使用 C++ 的 std::bitset 来优化常数，此时单次合并子集和可以优化到 O(w2ω)O\bigg(\dfrac{w^2}{\omega}\bigg)，其中 ω\omega 是 std::bitset 所用的字长，一般为 32 或 64。总时间复杂度 O(nw2ω)O\bigg(\dfrac{nw^2}{\omega}\bigg)。
另一种更狠的优化方式超出了本题的难度范围，本人赛场上懒得想了就直接写了这个：使用 FFT 优化单次合并子集和，可以做到 O(wlog⁡w)O(w \log w)。对于有兴趣的，这里讲解一下：
给定子集和 S,TS,T 生成 S+TS + T，你要优化的本质上是生成 s+ts + t 的过程。对 SS 构造生成函数 FS(z)=∑s∈SzsF_S(z) = \sum_{s \in S} z^s，此时有：
FS(z)FT(z)=∑s∈Szs∑t∈Tzt=∑s∈S,t∈Tzs+tF_S(z)F_T(z) = \sum_{s \in S} z^s \sum_{t \in T} z^t = \sum_{s \in S, t \in T} z^{s + t}
从而 FS(z)FT(z)F_S(z)F_T(z) 中 zkz^k 的系数表示有多少对 s,ts, t 满足 s+t=ks + t = k，若系数 ≥1\ge 1 则表示存在这样的 s,ts, t。
而计算 FS(z)FT(z)F_S(z)F_T(z) 显然就是多项式乘法，使用 FFT 就可以做到 O(wlog⁡w)O(w \log w) 的时间复杂度。此时本题的时间复杂度为 O(nwlog⁡w)O(nw \log w)，时间绰绰有余。

参考代码

CPP
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::vector;

using u64 = unsigned long long;

constexpr u64 P = 998'244'353;

template<class Grp, class Exp, class Ty>
Ty pow(Grp base, Exp exp, Ty id) {
	for(; exp; exp >>= 1, base *= base)
		if(exp & 1)
			id *= base;
	return id;
}

template<class Grp, class Exp, class Ty>
Ty& powass(Grp base, Exp exp, Ty &id) {
	for(; exp; exp >>= 1, base *= base)
		if(exp & 1)
			id *= base;
	return id;
}

struct Fp {

	u64 x;

	constexpr Fp(u64 val = 0) : x(val) {}

	Fp& operator+=(const Fp &other) {
		x += other.x;
		if(x >= P) x -= P;
		return *this;
	}
	Fp& operator-=(const Fp &other) {
		if(x < other.x) x += P;
		x -= other.x;
		return *this;
	}
	Fp& operator*=(const Fp &other) {
		x = x * other.x % P;
		return *this;
	}
	Fp& operator/=(const Fp &other) {
		return powass(other, P - 2, *this);
	}
	friend Fp operator+(Fp lhs, const Fp &rhs) { return lhs += rhs; }
	friend Fp operator-(Fp lhs, const Fp &rhs) { return lhs -= rhs; }
	friend Fp operator*(Fp lhs, const Fp &rhs) { return lhs *= rhs; }
	friend Fp operator/(Fp lhs, const Fp &rhs) { return lhs /= rhs; }
};

Fp prim(3);
Fp coprim = Fp(1) / prim;

vector<u64> graph[1001];
vector<u64> subset[1001];
bool visited[1001] = {};
u64 w[1001] = {};

template<class RanIt>
void FFT(RanIt arr, bool type) {
	for(int logseg = 0; logseg < 11; ++logseg) {
		size_t seg = 1ull << logseg;
		Fp omega = pow(type ? coprim : prim, (P - 1) >> (logseg + 1), Fp(1));
		for(RanIt lhs = arr; lhs != arr + 2048; lhs += (seg + seg)) {
			RanIt rhs = lhs + seg;
			Fp phi = Fp(1);
			for(size_t off = 0; off < seg; ++off) {
				Fp g = lhs[off];
				Fp hw = rhs[off] * phi;
				lhs[off] = g + hw;
				rhs[off] = g - hw;
				phi *= omega;
			}
		}
	}
	if(type) {
		Fp div = Fp(1) / Fp(2048);
		for(size_t i = 0; i < 2048; ++i)
			arr[i] *= div;
	}
}

vector<u64> subsetmerge(u64 u, const vector<u64> &lset, const vector<u64> &rset) {
	if(lset.size() * rset.size() < 2048) {
		bool contains[2001] = {};
		for(u64 x : lset) {
			for(u64 y : rset) {
				contains[x + y] = true;
			}
		}
		vector<u64> res;
		for(u64 z = 0; z <= w[u]; ++z)
			if(contains[z])
				res.push_back(z);
		return res;
	}
	std::array<Fp, 2048> lff{}, rff{};
	for(u64 x : lset) lff[x] = Fp(1);
	for(u64 x : rset) rff[x] = Fp(1);
	FFT(lff.begin(), false);
	FFT(rff.begin(), false);
	for(size_t i = 0; i < 2048; ++i)
		lff[i] *= rff[i];
	FFT(lff.begin(), true);
	vector<u64> res;
	for(u64 z = 0; z <= w[u]; ++z)
		if(lff[z].x)
			res.push_back(z);
	return res;
}

void dfs(u64 u) {
	visited[u] = true;
	bool isleaf = true;
	for(u64 v : graph[u]) {
		if(!visited[v]) {
			isleaf = false;
			dfs(v);
			subset[u] = subsetmerge(u, subset[u], subset[v]);
		}
	}
	if(isleaf) {
		subset[u].push_back(w[u]);
	}
}

int main() {

	size_t n;
	cin >> n; 
	for(u64 u = 1; u <= n; ++u) {
		cin >> w[u];
		subset[u].push_back(0);
	}
	for(u64 i = 1; i < n; ++i) {
		u64 u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	dfs(1);
	cout << subset[1].back();
	return 0;
}

评论

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

正在加载评论...