[入门]A104746.题解

显然对于一个有 $n$ 个顶点 $n-1$ 条边的连通图，一定是个树，而要将一个树上的任意两点出去任一条边使其不联通，一定需要删 $1$ 条边（请自行思考原因），故需要使 $k$ 个点不联通，则至少需要删除 $k-1$ 条边。

#include<bits/stdc++.h>
using namespace std;
signed main(){
    int n , k;
    cin >> n >> k;
    cout << max(k - 1 , 0);
    return 0;
}

讲个笑话，实际上上面这个代码是我在赛后想到的，在比赛时我想：“这不就是P2700逐个击破严格弱化版吗”，所以赛时我就把那题的代码复制过来改了一下...

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
#define int long long
int fa[N] , size[N] , color[N] , n , k , ans , sum;
struct node{
	int u , v , w;
	bool operator <(const node& other) const{
		return this->w > other.w;
	}
}edge[N];
void into(int n){
	for(int i = 0;i <= n;i ++){
		size[i] = 1;
		fa[i] = i;
	}
}
int Find(int x){
	if(x == fa[x]) return x;
	return fa[x] = Find(fa[x]);
}
int Get(int x){
	return color[Find(x)];
}
bool Can(int a , int b){
	int ga = Get(a) , gb = Get(b);
	return (ga == 0 || gb == 0  || ga == gb);
}
void Union(int x , int y){
	int rx = Find(x) , ry = Find(y);
	if(rx == ry){
		return;
	}
	if(size[ry] > size[rx]){
		swap(ry , rx);
	}
	fa[ry] = rx;
	size[rx] += size[ry];
	if(color[rx] == color[ry] || color[rx] == 0 && color[ry] == 0){
		return;
	}
	if(color[rx] == 0){
		color[rx] = color[ry];
	}else if(color[ry] == 0){
		color[ry] = color[rx];
	}
}
signed main(){
	cin >> n >> k;
	into(n);
	for(int i = 1;i <= k;i ++){
		int x;
		cin >> x;
		color[x] = i;
	}
	for(int i = 1;i < n;i ++){
		cin >> edge[i].u >> edge[i].v;
		edge[i].w = 1; 
		sum += edge[i].w;
	}
	for(int i = 1;i < n;i ++){
		if(Can(edge[i].u , edge[i].v)){
			ans += edge[i].w;
			Union(edge[i].u , edge[i].v);
		}
	}
	cout << sum - ans << endl;
	return 0;
}

实际上看着也不赖