TIOJ-1596

發表於 更新於 Disqus：

黑色騎士團終於決定了攻打大不列顛帝國的戰略。
在大不列顛帝國的國土當中，有著許多的城市，城市與城市之間會有道路相互連通。
在這些城市當中，有些特別的城市兼具有軍事堡壘的功能。
想要完全的佔領大不列顛帝國，必須要摧毀一些道路，讓軍事堡壘城市之間兩兩無法到達。
對於兩個城市，如果他們之間直接有道路連通，或著他們都同樣可以到達另一個城市，那我們說他們是可到達的。
摧毀道路是需要花錢的。經過了許久的研究，黑色騎士團發現對於每一條道路而言，摧毀它必然會造成某些城市之間不可到達。
請問如果要佔領大不列顛帝國，最少要花多少錢摧毀道路？

$n\le 10^5, c\le 2\times 10^4$

首先把某個重點畫起來：「對於每一條道路而言，摧毀它必然會造成某些城市之間不可到達。」
這一句話就代表了這張圖是一顆樹，所以原題目中的邊數 $m$ 肯定是 $n-1$。

所以就是給一棵帶邊權的樹，其中一些點是特殊點，問拔邊的最小花費使得特殊點不連通。

原本我是想要用 MST 那樣先把邊由小排到大再 greedy 不加邊，看起來很假解也很理所當然的 WA 了，可是我不知道為什麼><
總之後來的作法就是正規的樹DP。
令 $dp[u][1]$ 為以 $u$ 為根的子樹的答案，且 $u$ 目前所在的連通塊中有特殊點的最小花費，$dp[u][0]$ 則是沒有特殊點。

初始狀態就是如果 $u$ 是特殊點的話把 $dp[u][1]$ 設成 $0$ 且 $dp[u][0]$ 設成無限大，$u$ 不是特殊點的話就相反。

在合併子孫的答案時其實就考慮八種 case：哪邊有特殊點，以及要不要拔邊。
但其實只有兩邊都有特殊點時才需要拔邊，所以只有五種 case，列出轉移式同時應該就能自行體會了。
令 $u$ 為當前子樹，$v$ 為要合併進來的子孫，$c$ 為連接 $(u, v)$ 的邊權，則：
$$dp[u][1] = min(dp[u][1] + dp[v][0], dp[u][1] + dp[v][1] + c, dp[u][0] + dp[v][1])$$
$$dp[u][0] = min(dp[u][0] + dp[v][1] + c, dp[u][0] + dp[v][0])$$
答案會是 $min(dp[1][1],dp[1][0])$（我令 $1$ 號點為根）。

這樣就是妥妥的 $\mathcal{O}(N)$。

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
54
55
56
57
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
const ll LINF     = 4611686018427387903;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

const int N = 1e5 + 25;
ll dp[N][2];
bool is[N];
vector<pair<int, int>> edge[N];

void dfs(int u, int p) {
	dp[u][!is[u]] = ll(1e15);
	for(const auto &[v, c] : edge[u]) {
		if(v == p)
			continue;
		dfs(v, u);
		dp[u][1] = min({dp[u][1] + dp[v][0], dp[u][1] + dp[v][1] + c, dp[u][0] + dp[v][1]});
		dp[u][0] += min(dp[v][1] + c, dp[v][0]);
	}
}
signed main() {
	int n, m;
	cin >> n >> m;
	while(m--) {
		int u, v, c;
		cin >> u >> v >> c;
		edge[u].push_back({v, c});
		edge[v].push_back({u, c});
	}
	int k;
	cin >> k;
	while(k--) {
		int x;
		cin >> x;
		is[x] = true;
	}
	dfs(1, 1);
	cout << min(dp[1][1], dp[1][0]) << '\n';
}