L

直将所有敌袭存进一个队列，一天一天模拟即可，最终点1的值的相反数就是答案。

#include <bits/stdc++.h>
using namespace std;
// 2024 OneWan
vector<int> adj[100005];
int fa[100005];
long long val[100005];
long long temp[100005];
void dfs(int u, int p) {
	fa[u] = p;
	for (auto &to : adj[u]) {
		if (to == p) continue;
		dfs(to, u);
	}
}
void solve() {
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; i++) {
		adj[i].resize(0);
	}
	for (int i = 1 ; i < n ; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	queue<int> que;
	for (int i = 1 ; i <= n ; i++) {
		temp[i] = 0;
		cin >> val[i];
		if (val[i] < 0) {
			que.push(i);
		}
	}
	dfs(1, 0);
	set<int> st;
	long long ans = 0;
	while (!que.empty()) {
		while (!que.empty()) {
			int x = que.front();
			que.pop();
			if (x <= 1) continue;
			st.insert(fa[x]);
			temp[fa[x]] += val[x];
			val[x] = 0;
		}
		while (!st.empty()) {
			int x = *st.begin();
			st.erase(st.begin());
			if (x == 1) {
				ans = max(ans, -temp[x]);
				temp[x] = 0;
				continue;
			}
			if (llabs(temp[x]) > val[x]) {
				val[x] = temp[x] + val[x];
			}
			if (val[x] < 0) {
				que.push(x);
			}
			temp[x] = 0;
		}
	}
	cout << ans << "\n";
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

M

给定 个点和 条边的非联通图，问不使用这 条边能不能构成一个 个点的连通图，如果可以输出具体方案。

使用并查集将输入的非连通图进行连通块分类，如果有两个连通块 和 ，只需要 中的点连接 中的一点 和 中 的点连接 中的一点就能构成一个连通图。

可以证明最小数量为 条边。我们只需要 的第一个点不连接即可。

#include <bits/stdc++.h>
using namespace std;

// 2024 OneWan

int f[1000005];

int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	f[x] = y;
}
void solve() {
	int n, m;
	cin >> n >> m;
	iota(f, f + n + 1, 0);
	for (int i = 0 ; i < m ; i++) {
		int u, v;
		cin >> u >> v;
		merge(u, v);
	}
	vector<int> a;
	for (int i = 1 ; i <= n ; i++) {
		if (find(i) == i) {
			a.push_back(i);
		}
	}
	cout << "Yes\n";
	cout << n - 1 << "\n";
	for (int i = 1 ; i <= n ; i++) {
		if (i == a[0]) continue;
		if (find(i) == a[0]) {
			cout << i << " " << a[1] << "\n";
		} else {
			cout << i << " " << a[0] << "\n";
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}