最小顶点盖子以进入树中的k边缘

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] [t] [t]）\ geq K $ 。另外注意，只计算 $ dp $ for $ t \ leq k $ $ k 节点覆盖至少 $ k $ 边缘。

为了再现复发来计算DP，我们首先给出Knapsack函数：让 $ k（v_ {1}，\ dots，v_ {m}）$ 是一个阵列，这样

\ begin {等式*} K（v_ {1}，\ dots，v_ {m}）[t]=max_ {t_ {1} + \ dots + t_ {m}= t} \ sum_ {j= 1} ^ {m} v_ { j} [t_ {j}] \结束{arequation *}

注意： $ k（k（v_ {1}，\ dots，v_ {m-1}），v_ {m}）= k（v_ {1}，\点，v_ {m}）$ ，并且 $ k（a，b）$ 可以通过 $ \ mathcal {o}（| a | \ cdot | b |）$ 时间。因此，计算 $ k（v_ {1}，\ dots，v_ {m}）$ take $ \ mathcal {o} （\ sum_ {i= 2} ^ {m} | v_ {i} | \ sum_ {j= 1} ^ {j= 1} ^ {i-1} | v_ {j} | v_ {j} |）$ 时间，无论我们组合的顺序如何该集合。如果我们仅对DP的第一个 $ k $ 值感兴趣，复杂性下降到 $ \ mathcal {o}（\ sum_ {i= 2} ^ {m} | v_ {i} | \ min（k，\ sum_ {j= 1} ^ {i-1} | v_ {j} |）$ < / span>

let $ c_ {i} $ 是节点 $ i $ 的集合集 $ c_ {ij} $ 是 $ j $ th $ i $ 。然后 \ begin {ground *} 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] \结束{GALL *} 在哪里 \ begin {ground *} 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]）\\ \结束{GALL *} 使用此递归计算答案需要 $ \ mathcal {o}（nk）$ 时间。非正式地，这是因为在算法过程中，我们将单元素DP组合到表示整个树的DP中。我们最多为大多数 $ \ frac {n} {k} $ sets大小集合 $ k $ ，任何元素最多需要大多数 $ 2k $ 时间（如果元素 $ x \以$ 成本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

一个简单的解决方案是使用state $ dp（n，2，n）$ 。让 $ dp（i，0，j）$ 是我们可以使用 $ \ leq j的最大边缘数$ 子树中的节点植于节点 $ i $ ，节点 $ i $ 本身不是在顶点封面。让 $ dp（i，1，j）$ 是相同的，除了节点 $ i $ 之外在顶点封面。

过渡本身并不明显，但它可以使用背包状方法进行。考虑一个节点 $ i $ 的所有子项。使用 $ dp（ch，0，c）$ 和 $ dp（ch，1，c）$的所有值作为两个单独的背包中的项目：一个计算完整数组 $ dp（i，0）$ ，一个计算完整数组 $ DP（I，1）$ 。项目的成本是统一的<跨度类=“math-container”> $ c $ ，而这些值是以下内容：

如果计算 $ dp（i，0）$ ： $ dp（ch，0，c）$ 是 $ dp（ch，0，c）$ ; $ dp（ch，1，c）$ 是 $ dp（ch，1，c）+ 1 $ < / span>。
如果计算 $ dp（i，1）$ ： $ dp（ch，0，c）$ 是 $ dp（ch，0，c）+1 $ ; $ dp（ch，1，c）$ 是 $ dp（ch，1，c）+ 1 $ < / span>。

我们可以获得完整的数组 $ dp（i，0）$ 和 $ dp（i，1）$ 直接从背包的终点值（即 $ kn（last，j）$ 的所有 $ j $ ）。 knapsack有 $ o（\＃shows * n）$ 项目每个节点，并在 $ o（\＃shows * n * n）$ 每个节点。因此，解决方案的总复杂性是 $ O（n ^ 3）$ 。请注意，您必须略微修改传统的0-1背包，以防止两个代表同一节点的项目;这不是很困难。此外，在计算 $ dp（i，1）$ 阵列时，请注意节点 $ i $ 本身是顶点封面上的额外节点。

我还记得确定是否有解决方案比这一个更快地运行，但我不会怀疑它。