cobertura mínima de vértices para acessar k arestas em uma árvore

Question

Eu preciso encontrar o número mínimo de $N$ vértices em uma árvore com $N-1$ bordas, de modo que pelo menos $K$ arestas dessa árvore estão conectadas a esses vértices.

Por exemplo, se $N=9$ e $K=6$ e temos esta árvore:

   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

A resposta certa deveria ser $\matrm{min}=2$.

Alguma ideia?

Answer 1

Existe um $\mathcal{O}(nk)$ Abordagem DP.

Chame uma aresta coberta se selecionarmos um vértice próximo a ela.Enraíze a árvore em um vértice arbitrário $r$.Definir $DP[i][b][t]$ como o número máximo de arestas na subárvore do nó $i$ que pode ser coberto selecionando no máximo $t$ nós da subárvore.Se $b = 0$ não temos permissão para selecionar o nó $i$, e se $b = 1$ devemos selecioná-lo.

Se calcularmos este DP, podemos resolver o problema, pois o número mínimo de nós para cobrir $k$as bordas são as menores $t$ para qual $max(DP[r][0][t], DP[r][1][t]) \geq k$.Observe ainda que basta apenas calcular o $DP$ para $t \leq k$, como qualquer $k<n$ nós cobrem pelo menos $k$ arestas.

Para fornecer a recorrência para calcular o DP, primeiro fornecemos a função mochila:deixar $K(V_{1}, \pontos, V_{m})$ seja uma matriz tal que

\begin{equação*} K(V_{1}, \dots, V_{m})[t] = \max_{t_{1} + \dots + t_{m} = t} \sum_{j = 1}^{m} V_{j}[t_{j}] \end{equação*}

Observe que $K(K(V_{1}, \dots, V_{m-1}), V_{m}) = K(V_{1}, \dots, V_{m})$, e essa $K(A,B)$ pode ser calculado diretamente pela fórmula acima em $\mathcal{O}(|A| \cdot |B|)$ tempo.Portanto, calculando $K(V_{1}, \pontos, V_{m})$ leva $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \sum_{j = 1}^{i-1} |V_{j}|)$ tempo, independentemente da ordem em que combinamos os conjuntos.Se estivermos interessados ​​apenas no primeiro $k$ valores do DP, a complexidade cai para $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \min(k, \sum_{j = 1}^{i-1} |V_{j}|)) $

Deixar $C_{i}$ seja o conjunto de filhos do nó $i$, e $C_{ij}$ seja o $j$o filho de $i$.Então\begin{reunir*} DP[i][0][t] = K(V_{1}, \pontos, V_{|C_{i}|}) [t]\\ DP[i][1][t] = |C_{i}| + K(V'_{1}, \pontos, V'_{|C_{i}|}) [t-1] \end{reunir*}Onde\begin{reunir*} 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{reunir*}Calcular a resposta com esta recursão leva $\mathcal{O}(nk)$ tempo.Informalmente, isso ocorre porque, ao longo do algoritmo, combinamos DPs de elemento único em um DP que representa a árvore inteira.Fazemos no máximo $\frac{n}{k}$ combinações de conjuntos de tamanho $k$, e qualquer elemento nos custa no máximo US$ 2 mil$ tempo (se elemento $x\em A$ nos custa $|B|$ tempo ao calcular $K(A,B)$) antes de ser mesclado em um conjunto de tamanho $k$, então a quantidade total de trabalho é no máximo $\mathcal{O}(k^{2} \frac{n}{k} + k n) = \mathcal{O}(nk)$.Isso é fácil, mas tedioso de formalizar com indução.

#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

Uma solução simples é usar o estado $dp(n,2,n)$.Deixar $dp(i,0,j)$ seja o número máximo de arestas que podemos obter usando $\leq j$ nós na subárvore com raiz no nó $i$, com nó $i$ em si não está na cobertura do vértice.Deixar $dp(i,1,j)$ ser o mesmo, exceto o nó $i$ está incluído na cobertura do vértice.

A transição em si não é óbvia, mas pode ser feita usando um método semelhante ao da mochila.Considere todos os filhos do nó $i$.Use todos os valores de $dp(ch,0,c)$ e $dp(ch,1,c)$ como itens em duas mochilas separadas:um para calcular o array completo $dp(i,0)$ e um para calcular o array completo $dp(i,1)$.Os custos dos itens são uniformemente $c$, enquanto os valores são os seguintes:

Se calcular $dp(i,0)$:valor de $dp(ch,0,c)$ é $dp(ch,0,c)$;valor de $dp(ch,1,c)$ é $dp(ch,1,c)+1$.
Se calcular $dp(i,1)$:valor de $dp(ch,0,c)$ é $dp(ch,0,c)+1$;valor de $dp(ch,1,c)$ é $dp(ch,1,c)+1$.

Podemos obter os arrays completos $dp(i,0)$ e $dp(i,1)$ diretamente dos valores finais das Mochilas (ou seja, os valores de $kn(último,j)$ para todos $j$).A mochila tem $O(\#filhos *n)$ itens por nó e é executado em $O(\#filhos * n * n)$ por nó.Portanto, a complexidade total da solução é $O(n^3)$.Observe que você terá que modificar ligeiramente a mochila 0-1 tradicional para evitar que dois itens que representem o mesmo nó sejam levados;isso não é muito difícil.Além disso, ao calcular o $dp(i,1)$ array, observe que o nó $i$ em si é um nó extra na cobertura do vértice.

Tenho certeza de que existem soluções rodando mais rápido que esta, mas não duvido.