【图论】Linova and Kingdom—CF1336A

Linova and Kingdom—CF1336A
参考文章

思路

$1$ 号节点为根节点。很容易想到，工业城市在树的下边，旅游城市在树的上边。具体来说，如果节点 $u$ 是工业城市，那么它的子树的所有节点一定都是工业城市；如果节点 $u$ 是旅游城市，那么它到根节点的路径上的所有城市都是旅游城市。

我们先把所有城市认定为工业城市，然后在与工业城市直接相连的旅游城市中选出“将其变为工业城市提供的贡献值”最大的城市，并将其变为工业城市。

城市的贡献的计算方法：当前点的子树的节点数 - (当前点的深度 - 1)。

可以利用用优先队列来选出最佳的城市，然后再将新产生的满足条件的城市压入队列。

由于我们选出的“贡献点最大的城市”的前提是这个点（设为 $w$ 点）的子树上所有点都是工业城市，并且与根节点路径上的所有点都是旅游城市。那么如果后边的操作把 $w$ 点的子节点给变成了旅游城市，那么不就不满足这个条件了吗？

请认真考虑我们是如何计算计算一个边界处的旅游城市如果变为工业城市后可以提供的贡献的：当前点的子树的节点数 - (当前点的深度 - 1)。$w$ 的贡献是相对于“ $w$ 点及 $w$ 点到根节点路径上都是旅游城市的条件”，也就是这种计算贡献的方法考虑了上一个状态，并非独立计算某一个点的贡献。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;

int n, k;
int contri[N];

void solve() {
	cin >> n >> k;
	
	vector<vector<int>> g(n + 1);
	for (int i = 1; i <= n - 1; i ++) {
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	// 计算深度和子树中节点数量
	vector<int> deep(n + 1, -1), son_num(n + 1);
	auto dfs = [&] (auto dfs, int u) ->int {
		int sum = 1;
		for (auto v : g[u]) {
			if (deep[v] == -1) {
				deep[v] = deep[u] + 1;
				sum += dfs(dfs, v);
			}
		}
		son_num[u] = sum;
		return sum;
	};
	deep[1] = 1;
	dfs(dfs, 1);
	// 计算每个点的贡献
	for (int i = 1; i <= n; i ++) {
		son_num[i] --;
		contri[i] = son_num[i] - (deep[i] - 1);
	}
	
	int res = 0;
	k = n - k;
	vector<int> st(n + 1, 0); // 标记是否为旅游城市/已经来过
	
	priority_queue<PII, vector<PII>> q; // [贡献，节点] 降序优先队列
	q.emplace(contri[1], 1);
	while (not q.empty() && k --) {
		auto [f, s] = q.top(); q.pop();
		st[s] = 1;
		res += f;
		for (auto v : g[s]) {
			if (not st[v]) {
				q.emplace(contri[v], v);
			}
		}
	}
	
	cout << "         ";
	cout << res << "\n";
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
//	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71