[CF2063C] Remove Exactly Two 题解

前言

CF 好题。

正文

题意：有一个无根树，移除

2

点之后联通分量的个数最大是多少。

以下皆钦定度数为入度和出度的和。

设节点

u

的度数为

\text{deg}_u

，我们对依次移除的

2

点

i,j

进行分类讨论。

若 $i,j$ 不相邻：

断开 $i$ 点，树显然会变成有 $\text{deg}_i$ 个连通分量的图。

断开 $j$ 点，会再多出 $\text{deg}_j-1$ 个联通分量。为什么呢？因为在刚刚断开的 $\text{deg}_i$ 个分量里面必有 $1$ 个包含 $j$ （也包含其他的节点），断开 $j$ 不会影响这一个连通分量，因此会少多出来 $1$ 个连通分量。

答案为 $\text{deg}_i+\text{deg}_j-1$ 。
若 $i,j$ 相邻：

与 (1) 同样的逻辑，断开 $i$ 点，树还是会变成有 $\text{deg}_i$ 个连通分量的图。

但是，断开 $j$ 点，我们会比刚刚再少多出来一个连通分量，因为移除 $i$ 点的同时 $j$ 点的度数也 $-1$ 了。

答案为 $\text{deg}_i+\text{deg}_j-2$ 。

问题来了，那怎么实现呢？

具体的，我们枚举点

i

，然后根据上面的找出最大的满足条件的点

j

。

注意到我们需要一个能实时排序，插入和移除的数据结构，我这里用的是 std::set 和 std::multiset。

具体实现细节看代码。

Code

时间复杂度显然为

\Theta(n \log n)

。

CPP

#include <bits/stdc++.h>
#ifdef LOCAL
	#include "debug.h"
#else
	#define debug(...) 42
#endif
#define mkp make_pair
#define pb emplace_back
#define endl "\n"
using namespace std;
using ll = long long;
int n,m,t,cnt=0;
const int maxn=2e5+10;
const double eps=1e-6;

int deg[maxn];
vector<int> e[maxn];
void solve(){
	int ans=0;
	cin>>n;
	fill(deg+1,deg+1+n,0);
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		deg[u]++,deg[v]++;
		e[u].pb(v);
		e[v].pb(u);
	}
	set<pair<int,int>> st;
	for(int i=1;i<=n;i++) st.insert(mkp(deg[i],i));
	for(int i=1;i<=n;i++){
		multiset<int> mt;
		st.erase(mkp(deg[i],i));
		for(int v:e[i]){mt.insert(deg[v]);st.erase(mkp(deg[v],v));}
		int case2=deg[i]+*prev(mt.end())-2;
		if(st.size()){
			int case1=deg[i]+(*prev(st.end())).first-1;
			ans=max({ans,case1,case2});
		}else{ans=max({ans,case2});}
		st.insert(mkp(deg[i],i));
		for(int v:e[i])	st.insert(mkp(deg[v],v));
	}
	cout<<ans<<endl;
}

signed main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>t;
	while(t--) solve();
	return 0;
}

[CF2063C] Remove Exactly Two 题解

文章操作

前言

正文

Code

相关推荐

评论

[CF2063C] Remove Exactly Two 题解