题目链接：https://codeforces.com/contest/1917/problem/F
题意
有 \(n\) 条长度 \(l_i\) 的边，问它们是否能组成一棵 \(n + 1\) 个节点的树，使得树的直径长度为 \(d\)。\(n, d \le 2000\)。
题解
首先当然要存在一个边集 \(D\)，使得 \(\sum\limits_{i \in D} l_i = d\)，这可以使用背包判断。但这个条件不充分，例如第二个样例 \((\set{1, 4, 3, 4}, 7)\)，虽然存在 \(\set{2, 3}\) 使 $ l_2 + l_3 = 7$，但直径的长度不小于 \(8\)。
考虑对于一个给定的 \(D\) 如何构造这棵树。使用调整法等可证，最优的一个方案是找到直径的中点，把其它所有边都挂在中点上。那么\(D\) 可以成为直径的充要条件是：
- 存在一种划分 \(D = D_1 \cup D_2\)，使 \(\forall i \notin D, l_i \le \min(s_1 := \sum\limits_{i \in D_1} l_i, s_2:= \sum\limits_{i \in D_2} l_i)\)。
考虑如何计算。将 \(l_i\) 从小到大排序，枚举 \(\max\limits_{i \notin D} i\)，则应该满足如下条件：
-
\(\forall j > i, j \in D\)；
-
\(\exists x \ge l_i, x = \min(s_1, s_2)\)。
那么，对右侧预处理背包，计算 \(Suf = \set{\sum\limits_{j > i, j \in D_1} l_i}\)；对左侧使用双背包，计算 \(DP = \set{(\sum\limits_{j \le i, j \in D_1} l_i, \sum\limits_{j \le i, j \in D_2} l_i)}\)。枚举 \(i\)，记 $s = \sum\limits_{j > i} l_i $，则左侧还需要取总长度为 \(d-s\) 的边。提取出 \(Pre = \set{t| (t, d-s-t) \in DP}\)，可行的 \(s_1\) 就是位向量 \(Pre\) 与 \(Suf\) 的卷积。对 \(\forall l_i \le x \le \dfrac d 2\)，判断 \(s_1\) 是否在卷积中即可。
时间复杂度的瓶颈在于双背包的转移和位向量卷积计算。使用 bitset 加速计算，则它们都可以在 \(O(\dfrac {d^2} w)\) 内完成，总时间复杂度为 \(O(\dfrac{n d^2}{w})\)。
代码实现
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using bs = bitset<2023>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, d;
cin >> n >> d;
vector<int> l(n);
for (int &x : l) cin >> x;
ranges::sort(l);
int s = accumulate(l.begin(), l.end(), 0);
if (s == d) return void(cout << "Yes\n");
vector suf(n + 1, bs(1));
for (int i = n - 1; i >= 0; i--) {
suf[i] = suf[i + 1] | (suf[i + 1] << l[i]);
}
bool ans = false;
vector dp(d + 1, bs(0));
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
int x = l[i];
s -= x;
for (int s1 = d; s1 >= 0; s1--) {
dp[s1] |= dp[s1] << x;
if (s1 >= x) { dp[s1] |= dp[s1 - x]; }
}
bs vis{0}, pre{0};
for (int j = 0; j <= d - s; j++) pre[j] = dp[j][d - s - j];
// convolution (suf[i+1], pre)
for (int j = 0; j <= s && j <= d / 2; j++)
vis[j] = (pre & (suf[i + 1] >> (s - j))).any();
for (int j = s; j <= d / 2; j++)
vis[j] = (pre & (suf[i + 1] << (j - s))).any();
for (int s1 = x; s1 <= d / 2; s1++) { ans |= vis[s1]; }
}
cout << (ans ? "Yes" : "No") << "\n";
}