【题解】HarkerRank - Matrix

题目

https://www.hackerrank.com/challenges/matrix/problem

题意

在一棵有边权的树上,要求去掉一些边,使得给定的若干个点之间两两不连通,求这些边的最小边权和。

题解

  • 树形 dp
  • $f[u]$ 表示子树上所有给定点与当前点不连通的最小代价(自己解决所有问题)。
  • $g[u]$ 表示子树上恰有一个给定点与当前点联通的最小代价(自己几乎解决了问题,但还要父亲帮忙)。
  • $t_v = \min{w_{uv}+g[v],f[v]}​$ 表示解决儿子 $v​$ 的最小代价。
  • $s=\sum t_v$ 表示解决除自己外所有问题的代价。
  • $m = \max{t_v-g[v]}$ 表示所有儿子中少解决一个所能省下的最大代价。
  • 分情况
    • 如果当前结点是需要隔离的:$f[u]=\inf, g[u]=s$
    • 如果当前点不需要隔离:$f[u]=s, g[u]=s-m$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (false)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E6 + 100;
const LL INF = 1E18;
LL f[maxn], g[maxn]; // f: include, g: exclude
struct E {
LL to, d;
};
bool b[maxn];
vector<E> G[maxn];

void go(LL u, LL fa) {
LL s = 0, m = 0;
for (E& e: G[u]) {
LL v = e.to;
if (v == fa) continue;
go(v, u);
LL t = min(f[v], g[v] + e.d);
s += t;
m = max(m, t - g[v]);
}
if (b[u]) { f[u] = INF; g[u] = s; }
else { f[u] = s; g[u] = s - m; }
}

int main() {
int n, k;
cin >> n >> k;
FOR (_, 1, n) {
LL u, v, d;
scanf("%lld%lld%lld", &u, &v, &d);
G[u].push_back({v, d});
G[v].push_back({u, d});
}
while (k--) {
LL u; scanf("%lld", &u);
b[u] = true;
}
go(1, -1);
cout << g[1] << endl;
}