CF1917F Construct Tree 题解

题目链接：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";
}