# Q：用最小代价孤立加权树中的一些顶点

Suppose we are given a weighted tree and some set of vertices of that tree. The problem is to isolate those vertices(e.g. there should not be paths between them) by removing edges from the tree, such that the sum of the weights of removed edges is minimal.

I have been trying to solve this problem for about two hours, then I found solution in C++, but there was no explanation. As I understood it uses Dynamic Programming technique.

My question is what is the basic idea of solving this problem?

Thanks!

Here is the solution.

``````#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

#define PB push_back
#define MP make_pair

typedef long long LL;
const int MAXN = 100005;
const LL inf = 1LL << 55;
int N, K;
LL dp[MAXN][2];

void dfs(int u, int fa) {
dp[u][1] = 0;
dp[u][0] = bad[u] ? inf : 0;

for (int i = 0; i < adj[u].size(); i++) {

if (v != fa) {
dfs(v, u);
dp[u][1] += min(dp[v][0], dp[v][1] + w);
dp[u][1] = min(dp[u][1], dp[u][0] + dp[v][1]);

dp[u][0] += min(dp[v][0], dp[v][1] + w);
}
}
}

int main() {
cin >> N >> K;

for (int i = 1; i < N; i++) {
int a, b, c;
cin >> a >> b >> c;
}

for (int i = 0; i < K; i++) {
int x;
cin >> x;
}

dfs(0, -1);
LL ret = min(dp[0][0], dp[0][1]);

cout << ret << endl;

return 0;
}
``````

``````#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

#define PB push_back
#define MP make_pair

typedef long long LL;
const int MAXN = 100005;
const LL inf = 1LL << 55;
int N, K;
LL dp[MAXN][2];

void dfs(int u, int fa) {
dp[u][1] = 0;
dp[u][0] = bad[u] ? inf : 0;

for (int i = 0; i < adj[u].size(); i++) {

if (v != fa) {
dfs(v, u);
dp[u][1] += min(dp[v][0], dp[v][1] + w);
dp[u][1] = min(dp[u][1], dp[u][0] + dp[v][1]);

dp[u][0] += min(dp[v][0], dp[v][1] + w);
}
}
}

int main() {
cin >> N >> K;

for (int i = 1; i < N; i++) {
int a, b, c;
cin >> a >> b >> c;
}

for (int i = 0; i < K; i++) {
int x;
cin >> x;
}

dfs(0, -1);
LL ret = min(dp[0][0], dp[0][1]);

cout << ret << endl;

return 0;
}
``````

Formally, the problem is, given an acyclic undirected graph with weighted edges, together with a set of terminal vertices, find the minimum set of edges whose removal means that, for all pairs of distinct terminals, those terminals are no longer connected.

Root the graph arbitrarily and treat it as a general tree. We run a dynamic program that operates bottom-up on the vertices. Each vertex u has two labels: dp[u][0] is the minimum weight of edges to be removed in the subtree rooted at u so that no terminal in the subtree is connected to another terminal or to u, and dp[u][1] is the minimum removal weight that leaves exactly one subtree terminal connected to u. We have a recurrence

``````           { infinity                  if v is a terminal
dp[u][0] = {       sum       dp[v][0]  otherwise
{ children v of u

dp[u][1] =       min       dp[v][1] +          sum          min(dp[w][0], dp[w][1] + weight(uw)),
children v of u            other children w of v
``````

taking an empty min to be infinity.

``````           { infinity                  if v is a terminal
dp[u][0] = {       sum       dp[v][0]  otherwise
{ children v of u

dp[u][1] =       min       dp[v][1] +          sum          min(dp[w][0], dp[w][1] + weight(uw)),
children v of u            other children w of v
``````

c++  algorithm  dynamic-programming