Минимальная вершина для доступа к краям в дереве

Question

Мне нужно найти минимальный номер из $ n $ вершины на дереве с $ N-1 $ ребра, так что, по крайней мере, $ k $ жгты этого дерева подключены к этим вершинам.

Например, если $ n= 9 $ и $ k= 6 $ и у нас есть этоДерево:

   Edges  |  Vertice #1  | Vertice #2
     1            1          2
     2            1          3
     3            1          4
     4            2          5
     5            2          6
     6            3          7
     7            4          8
     8            4          9

.

Правильный ответ должен быть $ \ Mathrm {min}= 2 $ .

Любые мысли?

Answer 1

Есть $ \ mathcal {o} (nk) $ подход DP.

Вызовите краю покрыты, если вы выберете вершину рядом с ней. Корень дерева на произвольной вершине $ R $ . Определите $ dp [i] [b] [t] $ как максимальное количество ребер в подметке узла $ I $ , который можно покрыть, выбрав на большинстве $ t $ узлы из поддерева. Если $ B= 0 $ нам не разрешено выбирать узел $ i $ , а если $ B= 1 $ Мы должны выбрать его.

Если мы рассчитаем этот DP, мы можем решить проблему, так как минимальное количество узлов для покрытия $ K $ - это самый маленький $ t $ для которого $ max (dp [r] [0] [t], dp [r] [1] [t]) \ geq k $ . Дальнейшее обратите внимание, что достаточно, чтобы рассчитать только $ dp $ для $ t \ leq k $ , как любой $ k Узлы покрывают как минимум $ K $ ребра.

Чтобы дать рецидиве, чтобы рассчитать DP, мы сначала дам функцию knaxack-функции: пусть $ k (v_ {1}, \ dots, v_ {m}) $ Будьте массива такого, что

\ Начало {Уравнение *} K (v_ {1}, \ dots, v_ {m}) [t]=max_ {t_ {1} + \ dots + t_ {m}= t} \ sum_ {j= 1} ^ {m} v_ { j} [t_ {j}] \ end {уравнение *}

Обратите внимание, что $ k (k (v_ {1}, \ dots, v_ {m-1}), v_ {m})= k (v_ {1}, \ dots, v_ {m}) $ , и что $ k (a, b) $ можно напрямую рассчитать по вышеуказанной формуле в $ \ mathcal {o} (| a | \ cdot | b |) $ время. Отсюда расчет $ k (v_ {1}, \ dots, v_ {m}) $ требует $ \ mathcal {o} (\ sum_ {i= 2} ^ {m} | v_ {i} | \ sum_ {j= 1} ^ {i-1} | v_ {j} |) $ Время независимо от того, Наборы. Если мы заинтересованы только в первом $ k $ значения DP, сложность падает на $ \ mathcal {o} (\ sum_ {i= 2} ^ {m} | v_ {i} | \ min (k, \ sum_ {j= 1} ^ {i-1} | v_ {j} |)) $ < / span>

Пусть $ C_ {i} $ Будьте набор детей узла $ i $ , а также $ c_ {ij} $ Будьте $ J $ TH CHARDE of $ i $ . потом \ Начало {Соберите *} Dp [i] [0] [t]= k (v_ {1}, \ dots, v_ {| c_ {i} |}) [t] \\ DP [I] [1] [T]= | C_ {I} | + K (v '_ {1}, \ dots, v' _ {| C_ {i} |}) [T-1] \ end {shark *} Где \ Начало {Соберите *} V_ {j} [t]=max (dp [c_ {ij}] [0] [t], dp [c_ {ij}] [1] [t] + 1) \\ V '_ {j} [t]=max (dp [c_ {ij}] [0] [t], dp [c_ {ij}] [1] [t]) \\ \ end {shark *} Расчет ответа с этой рекурсией требуется $ \ mathcal {o} (nk) $ time. Неофициально это потому, что в течение хода алгоритма мы объединяем одноэлементную DPS в DP, представляющее все дерево. Мы делаем на большинстве $ \ frac {n} {k} $ Комбинации наборов размеров $ k $ И любой элемент стоит нам максимально $ 2k $ Время (если элемент $ x \ in in $ стоит US $ | B | $ Время при расчете $ k (a, b) $ ) до того, как он будет объединен в набор размеров $ k $ , поэтому общая сумма работы находится на большинстве $ \ mathcal {o} (k ^ {2} \ frac {n} {k} + kn)=mathcal {o} (nk) $ . Это легко, но утомительно формализовать с индукцией.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int INF = (int)1e9 + 7;

vector<int> knapsack(const vector<int> a, const vector<int> b, int k) {
    int n = a.size();
    int m = b.size();
    vector<int> c(n+m-1, -INF);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) c[i+j] = max(c[i+j], a[i] + b[j]);
    }
    if (c.size() > k) c.resize(k);
    return c;
}

pair<vector<int>, vector<int>> dfs(int i, int p, int k, const vector<vector<int>>& g) {
    vector<int> dp0 = {0, 0};
    vector<int> dp1 = {-INF, (int)g[i].size() - (p != -1)};
    for (auto t : g[i]) {
        if (t == p) continue;
        vector<int> dp0_t, dp1_t;
        tie(dp0_t, dp1_t) = dfs(t, i, k, g);
        int m = dp0_t.size();

        vector<int> off0(m), off1(m);
        for (int j = 0; j < m; ++j) off0[j] = max(dp0_t[j], dp1_t[j] + 1);
        for (int j = 0; j < m; ++j) off1[j] = max(dp0_t[j], dp1_t[j]);
        dp0 = knapsack(dp0, off0, k+1);
        dp1 = knapsack(dp1, off1, k+1);
    }
    return {dp0, dp1};
}

int minCover(int k, const vector<vector<int>>& g) {
    vector<int> dp0, dp1;
    tie(dp0, dp1) = dfs(0, -1, k, g);
    for (int i = 0;; ++i) {
        if (max(dp0[i], dp1[i]) >= k) return i;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int t = minCover(k, g);
    cout << t << '\n';
}

.

Answer 2

Простое решение - использовать состояние $ dp (n, 2, n) $ . Пусть $ dp (i, 0, j) $ Будьте максимальным количеством ребер, которые мы можем получить с помощью $ \ leq j $ Узлы в поддеревом коренном узере в узле $ i $ , с узлом $ i $ сам не быть в крышке вершины. Пусть $ dp (i, 1, j) $ Будьте одинаковы, кроме узела $ i $ включено в крышке вершины.

Сам переход не очевиден, но это может быть сделано с использованием метода Knaxack-Alke. Рассмотрим все дети узла $ i $ . Используйте все значения $ dp (ch, 0, c) $ и $ dp (ch, 1, c) $ как элементы в двух отдельных рюкзаках: один для расчета полного массива $ DP (I, 0) $ и один для расчета полного массива $ DP (I, 1) $ . Затраты на элементы равномерно $ C $ , а значения следующие:

Если вычисление $ dp (i, 0) $ : значение $ dp (ch, 0, c) $ - $ dp (ch, 0, c) $ ; Значение $ dp (ch, 1, c) $ IS $ DP (CH, 1, C) + 1 $ < / span>.

Если вычисление $ dp (i, 1) $ : значение $ dp (ch, 0, c) $ Является ли $ dp (ch, 0, c) +1 $ ; Значение $ dp (ch, 1, c) $ IS $ DP (CH, 1, C) + 1 $ < / span>.

Мы можем получить полные массивы $ dp (i, 0) $ и $ dp (i, 1) $ непосредственно из конечных значений knaxacks (то есть значения $ kn (last, j) $ для всех $ j $ ). Knaxackack имеет $ O (\ # DEALS * N) $ элементы на узел и работает в $ O (\ # дети * n * n) $ на узел. Следовательно, общая сложность решения составляет $ O (n ^ 3) $ . Обратите внимание, что вам придется немного изменять традиционный рюкзак 0-1, чтобы предотвратить принятие двух элементов, которые представляют один и тот же узел; Это не очень сложно. Кроме того, при расчете $ dp (i, 1) $ Array, обратите внимание, что узел $ i $ Сам дополнительный узел на крышке вершины.

Я отмечаю, что есть решения, работающие во времени быстрее, чем этот, но я бы не сомневался в этом.