cobertura mínima de vértices para acceder a k bordes en un árbol

Question

Necesito encontrar el número mínimo de $N$ vértices de un árbol con $N-1$ bordes, de modo que al menos $k$ Los bordes de ese árbol están conectados a estos vértices.

Por ejemplo, si $N=9$ y $K=6$ y tenemos este árbol:

   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

La respuesta correcta debería ser $\mathrm{min}=2$.

¿Alguna idea?

Answer 1

Hay un $\mathcal{O}(nk)$ Enfoque del DP.

Llamamos a una arista cubierta si seleccionamos un vértice al lado de ella.Arraigar el árbol en un vértice arbitrario. $r$.Definir $DP[i][b][t]$ como el número máximo de aristas en el subárbol del nodo $yo$ que se puede cubrir seleccionando como máximo $t$ nodos del subárbol.Si $b = 0$ no se nos permite seleccionar el nodo $yo$, y si $b = 1$ debemos seleccionarlo.

Si calculamos este DP, podemos resolver el problema, ya que el número mínimo de nodos a cubrir $k$los bordes son los más pequeños $t$ para cual $max(DP[r][0][t], DP[r][1][t]) \geq k$.Tenga en cuenta además que basta con calcular únicamente el $DP$ para $t\leqk$, como cualquier $ k < n $ Los nodos cubren al menos $k$ bordes.

Para dar la recurrencia para calcular el DP, primero damos la función de mochila:dejar $K(V_{1}, \puntos, V_{m})$ ser una matriz tal que

Begin {Ecation*} k (v_ {1}, dots, v_ {m}) [t] = max_ {t_ {1} + dots + t_ {m} = t} sum_ {j = 1} ^{m} v_ {j} [t_ {j}] end {ecuación*}

Tenga en cuenta que $K(K(V_{1}, \dots, V_{m-1}), V_{m}) = K(V_{1}, \dots, V_{m})$, y eso $K(A,B)$ se puede calcular directamente mediante la fórmula anterior en $\mathcal{O}(|A| \cdot |B|)$ tiempo.Por lo tanto calculando $K(V_{1}, \puntos, V_{m})$ acepta $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \sum_{j = 1}^{i-1} |V_{j}|)$ tiempo independientemente del orden en el que combinemos los conjuntos.Si sólo nos interesa el primero $k$ valores del DP, la complejidad cae a $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \min(k, \sum_{j = 1}^{i-1} |V_{j}|)) ps

Dejar $C_{i}$ ser el conjunto de hijos del nodo $yo$, y $C_{ij}$ ser el $j$º hijo de $yo$.Entoncesbegin {reunir*} 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 {reunir*}Dóndebegin {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 {recopilar*}Calcular la respuesta con esta recursividad requiere $\mathcal{O}(nk)$ tiempo.De manera informal, esto se debe a que en el transcurso del algoritmo, combinamos DP de un solo elemento en un DP que representa el árbol completo.lo hacemos como mucho $\frac{n}{k}$ combinaciones de conjuntos de tamaño $k$, y cualquier elemento nos cuesta como mucho $2k$ tiempo (si el elemento $x \en A$ nos cuesta $|B|$ tiempo al calcular $K(A,B)$) antes de fusionarse en un conjunto de tamaño $k$, por lo que la cantidad total de trabajo es como máximo $\mathcal{O}(k^{2} \frac{n}{k} + k n) = \mathcal{O}(nk)$.Esto es fácil pero tedioso de formalizar mediante inducción.

#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

Una solución simple es usar el estado $ dp (n, 2, n) $ . Deje que $ DP (I, 0, J) $ sea el número máximo de bordes que podemos obtener usando $ \ leq j $ nodos en el subtrete enraizado en el nodo $ i $ , con nodo $ i $ mismo No estar en la cubierta del vértice. Deje que $ DP (I, 1, J) $ sea el mismo, excepto el nodo $ i $ está incluido en la cubierta del vértice.

La transición en sí no es obvia, pero se puede hacer utilizando un método similar a la mochila. Considere a todos los niños del nodo $ i $ . Utilice todos los valores de $ dp (CH, 0, C) $ y $ dp (CH, 1, C) $ como elementos en dos mochilas separadas: una para calcular la matriz completa $ dp (I, 0) $ y uno para calcular la matriz completa $ DP (I, 1) $ . Los costos de los artículos son uniformemente $ C $ , mientras que los valores son los siguientes:

Si calcula $ dp (i, 0) $ : Valor de $ dp (CH, 0, C) $ es $ dp (CH, 0, C) $ ; Valor de $ dp (CH, 1, C) $ es $ dp (CH, 1, C) + 1 $ < / span>.
Si calcula $ DP (I, 1) $ : Valor de $ dp (CH, 0, C) $ es $ dp (CH, 0, C) +1 $ ; Valor de $ dp (CH, 1, C) $ es $ dp (CH, 1, C) + 1 $ < / span>.

Podemos obtener las matrices completas $ dp (I, 0) $ y $ dp (I, 1) $ directamente desde los valores de extremo de las mochilas (es decir, los valores de $ kn (ultimo, j) $ para todos $ j $ ). La mochila tiene $ o (\ # niños * n) $ artículos por nodo, y se ejecuta en $ o (\ # niños * n * n) $ por nodo. Por lo tanto, la complejidad total de la solución es $ o (n ^ 3) $ . Tenga en cuenta que tendrá que modificar ligeramente la mochila de 0-1 tradicional para evitar que se tomen los mismos artículos que representen el mismo nodo; Esto no es muy difícil. Además, al calcular el $ dp (i, 1) $ matriz, tenga en cuenta que el nodo $ i $ En sí mismo es un nodo extra en la cubierta del vértice.

Estoy seguro de que, si hay soluciones que se ejecutan en tiempo más rápido que este, pero no lo dudaría.