Разбор задачи «Сборка диагностической сети»

Идея задачи

Нам дано n кабелей с длинами l1, l2, ..., ln. Нужно понять, можно ли из них собрать дерево на n + 1 вершинах так, чтобы диаметр этого дерева был ровно d.

Напомним, что диаметр дерева — это максимальное расстояние между двумя вершинами дерева.

На первый взгляд задача кажется конструктивной: нужно как-то «собрать» дерево из рёбер. Но на самом деле строить дерево явно не требуется. Достаточно понять, существует ли подходящее разбиение рёбер.

Главное наблюдение

Рассмотрим путь, который является диаметром дерева. Сумма длин всех рёбер на этом пути должна быть ровно d.

Пусть мы выбрали некоторую вершину на этом диаметре как «центр разветвления». Тогда диаметр разбивается на две части:

• в одну сторону суммарная длина равна x,
• в другую сторону суммарная длина равна d - x.

Теперь посмотрим на любое ребро, которое не лежит на диаметре. Если мы хотим подвесить его как ветку от этой вершины, то его длина не должна быть слишком большой. Иначе можно будет пройти от конца этой ветки до одного из концов диаметра и получить путь длины больше d, а это запрещено.

Значит, каждое ребро вне диаметра должно иметь длину не больше

min(x, d - x).

Итак, задача сводится к следующему:

1. выбрать некоторое подмножество рёбер, которое пойдёт в диаметр, так чтобы их сумма была d;
2. разбить эти рёбра на две части с суммами x и d - x;
3. убедиться, что все остальные рёбра имеют длину не больше min(x, d - x).

Почему достаточно смотреть только на самые большие рёбра

Отсортируем длины:

a1 <= a2 <= ... <= an

Самые важные рёбра — самые длинные. Именно они сильнее всего ограничивают возможную структуру дерева.

Оказывается, достаточно рассмотреть три случая.

Случай 1. Два самых больших ребра лежат на диаметре

То есть a[n-1] и a[n] входят в диаметр.

Тогда оставшиеся рёбра не длиннее a[n-1]. Если одно большое ребро идёт в одну сторону от точки разбиения, а другое — в другую, то внешние рёбра уже не смогут «сломать» диаметр.

Остаётся только понять, можно ли из остальных рёбер добрать нужную сумму:

d - a[n-1] - a[n]

Это обычная задача subset sum.

Случай 2. Самое большое ребро на диаметре, второе по величине — вне диаметра

То есть a[n] лежит на диаметре, а a[n-1] — нет.

Тогда нужно из меньших рёбер выбрать две непересекающиеся группы с суммами:

• x,
• d - a[n] - x

После этого ребро a[n] добавляется к первой части, и стороны диаметра становятся:

• x + a[n],
• d - a[n] - x

Чтобы ребро a[n-1] можно было повесить вне диаметра, должно выполняться:

a[n-1] <= min(x + a[n], d - a[n] - x)

Случай 3. Самое большое ребро вообще не лежит на диаметре

То есть a[n] — внешнее ребро.

Тогда диаметр целиком собирается из первых n - 1 рёбер. Нужно выбрать две непересекающиеся группы с суммами:

• x,
• d - x

и дополнительно должно выполняться:

a[n] <= min(x, d - x)

Тогда все остальные внешние рёбра тоже точно подойдут, потому что они не длиннее a[n].

Какой DP нужен

В первом случае нам нужен обычный subset sum.

Во втором и третьем случаях нужно уметь выбирать две непересекающиеся группы. Для этого удобно сделать DP по двум суммам.

Пусть

f[j][k] = true, если среди уже рассмотренных рёбер можно выбрать две непересекающиеся группы с суммами j и k.

Тогда для нового ребра длины w есть три варианта:

• не брать его,
• положить в первую группу,
• положить во вторую группу.

Такой DP удобно хранить как массив битсетов:

• f[j] — битсет по всем k.

Тогда переходы становятся быстрыми.

Почему решение работает

Мы разобрали все принципиально разные положения самых длинных рёбер:

• оба лежат на диаметре;
• только самое большое лежит на диаметре;
• самое большое вообще не лежит на диаметре.

Других вариантов для максимального внешнего ребра нет.

Для каждого случая DP проверяет, можно ли:

• набрать суммарную длину диаметра d,
• разбить его на две стороны,
• сделать так, чтобы все остальные рёбра были не длиннее меньшей из этих двух сторон.

Если хотя бы в одном из случаев это удаётся, ответ Yes. Иначе — No.

Оценка сложности

Поскольку d <= 2000, можно позволить себе DP по суммам до d.

Итоговая сложность решения:

• примерно O(n * d^2 / word_size) при использовании битсетов,
• что укладывается в ограничения.

По памяти тоже всё проходит, потому что d небольшой.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

static const int MAXD = 2005;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, d;
        cin >> n >> d;

        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        sort(a.begin() + 1, a.end());

        vector<bitset<MAXD>> f(d + 1);
        bitset<MAXD> g;

        for (int i = 0; i <= d; i++) {
            f[i].reset();
        }
        g.reset();

        f[0].set(0);
        g.set(0);

        bool ok = false;

        for (int i = 1; i < n; i++) {
            if (i == n - 1) {
                if (a[n - 1] + a[n] <= d && g.test(d - a[n - 1] - a[n])) {
                    ok = true;
                }

                for (int x = 0; x <= d - a[n] && !ok; x++) {
                    int y = d - a[n] - x;
                    if (y < 0 || y > d) continue;
                    if (f[x].test(y) && a[n - 1] <= min(x + a[n], y)) {
                        ok = true;
                    }
                }
            }

            if (ok) break;

            for (int j = d; j >= 0; j--) {
                f[j] |= (f[j] << a[i]);
                if (j >= a[i]) {
                    f[j] |= f[j - a[i]];
                }
            }

            g |= (g << a[i]);
        }

        if (!ok) {
            for (int x = a[n]; x <= d - a[n]; x++) {
                if (f[x].test(d - x)) {
                    ok = true;
                    break;
                }
            }
        }

        cout << (ok ? "Yes" : "No") << '\n';
    }

    return 0;
}

Реализация на Python

В Python ту же идею удобно реализовать через целые числа как битовые маски.

• g — битовая маска для обычного subset sum;
• f[x] — целое число, в котором установлен бит y, если можно набрать две непересекающиеся группы сумм x и y.

import sys


def solve():
    input = sys.stdin.readline
    t = int(input())

    for _ in range(t):
        n, d = map(int, input().split())
        a = list(map(int, input().split()))
        a.sort()

        f = [0] * (d + 1)
        g = 1
        f[0] = 1

        ok = False

        for i in range(n - 1):
            if i == n - 2:
                if a[n - 2] + a[n - 1] <= d:
                    need = d - a[n - 2] - a[n - 1]
                    if (g >> need) & 1:
                        ok = True

                if not ok:
                    limit = d - a[n - 1]
                    for x in range(limit + 1):
                        y = d - a[n - 1] - x
                        if y < 0 or y > d:
                            continue
                        if ((f[x] >> y) & 1) and (a[n - 2] <= min(x + a[n - 1], y)):
                            ok = True
                            break

            if ok:
                break

            w = a[i]
            new_f = f[:]

            for j in range(d, -1, -1):
                val = f[j]
                if val == 0:
                    continue

                new_f[j] |= (val << w)
                if j + w <= d:
                    new_f[j + w] |= val

            f = new_f
            g |= (g << w)

        if not ok:
            for x in range(a[n - 1], d - a[n - 1] + 1):
                y = d - x
                if (f[x] >> y) & 1:
                    ok = True
                    break

        print("Yes" if ok else "No")


if __name__ == "__main__":
    solve()

Разбор переходов DP

Разберём внимательно, что происходит в f.

Пусть мы рассматриваем очередное ребро длины w.

Если уже можно было собрать две группы с суммами j и k, то теперь можно:

1. ничего не делать — состояние остаётся;
2. положить w в первую группу — получим сумму j + w и k;
3. положить w во вторую группу — получим сумму j и k + w.

Именно это и кодируется переходами.

В C++ с битсетами это выглядит очень компактно:

f[j] |= (f[j] << a[i]);
if (j >= a[i]) {
    f[j] |= f[j - a[i]];
}

Здесь:

• f[j] << a[i] означает «добавить текущее ребро во вторую группу»;
• f[j - a[i]] переходит в f[j], что означает «добавить текущее ребро в первую группу».

На что обратить внимание

1. Нужно именно две непересекающиеся группы

Нельзя использовать одно и то же ребро сразу в обеих частях диаметра. Поэтому и нужен аккуратный DP, а не просто два независимых subset sum.

2. Проверять только сумму d недостаточно

Даже если можно выбрать рёбра с суммой d, это ещё не гарантирует ответ Yes. Нужно ещё уметь разбить их на две стороны так, чтобы внешние рёбра не увеличили диаметр.

3. Самые длинные рёбра определяют ответ

Именно поэтому сортировка и разбор нескольких случаев дают сильное упрощение задачи.

Небольшой пример рассуждения

Пусть длины такие:

1, 1, 2, 4, а d = 7.

Можно взять рёбра 1 + 2 + 4 = 7 в диаметр. Тогда одна сторона может иметь длину 4, а другая — 3. Оставшееся ребро длины 1 не превосходит 3, значит, его можно подвесить как ветку. Ответ Yes.

А если бы вне диаметра осталось ребро длины, например, 5, то подвесить его уже было бы нельзя: тогда путь от его конца до противоположного конца диаметра стал бы длиннее 7.

Итог

В этой задаче главное — не пытаться строить дерево напрямую. Нужно понять, какие рёбра могут лежать на диаметре и как разбить этот диаметр на две стороны.

После этого задача превращается в аккуратный DP по суммам.

Это хороший пример задачи, где:

• геометрия дерева сводится к числовым условиям,
• важнейшую роль играет анализ самых больших элементов,
• а финальная реализация опирается на bitset DP.

Если хорошо понять эту идею, многие похожие задачи на разбиение и построение дерева станут заметно понятнее.