专栏文章

题解：CF2131D Arboris Contractio

yyys_wys
CF2131D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mioaqpht
此快照首次捕获于
2025/12/02 16:08
3 个月前
此快照最后确认于
2025/12/02 16:08
3 个月前
查看原文

题意

给定一棵无根树 TT，有 nn 个节点，现有一种操作：
  1. 选择两个节点 s,t∈Ts,t\in T。
  2. 把 ss 到 tt 的简单路径上的每一个节点，断掉原来位于这条链上的边，直接连到 ss 节点上
问最少多少次操作才能让 n−1n-1 个节点全部连到另一个节点上

思路

我们注意到这样一个性质：
对于一个选出的根节点 rt∈Trt\in T，其叶子节点中深度不为 11（就是不直接连接 rtrt 的叶子节点）都需要至少一次操作来将其连到 rtrt 上，同时路径上的其它点也一起连好了。
然而，一次操作只能改变一个叶子节点，因为我们必须设定 ss 为 rtrt，否则只会更劣。
这说明什么？
这说明我们只需要操心叶子节点。
更进一步，操作次数就是需要动的叶子节点个数，也就是不直连 rtrt 的叶子节点个数。
问题来了，对于每一个 rtrt，我们去求这个东西，是 O(n2)O(n^2) 的，怎么办？
正难则反，我们只需要先从任意一点出发，求总叶子节点个数，然后对于每一个 rtrt，分别更新答案。
设以 rtrt 为根的操作数为 ansrtans_{rt}，总叶子节点个数为 numnum，以该节点为根时深度为 11 的叶子节点个数为 d1rtd1_{rt}，则有 ∀rt∈T,ansrt=num−d1rt\forall rt\in T, ans_{rt}=num-d1_{rt}
所以我们只要对每一个节点算出答案，再求 min⁡\min 就可以了。

复杂度

时间复杂度

我们考虑预处理出总叶子节点个数，以及每一个节点直连叶子节点个数，这是 O(n)O(n) 的。
对于每一个节点，算该节点为根答案所需的两个参数我们已经计算好，就是 O(1)O(1) 的。
总共 nn 个节点，每个节点 O(1)O(1)，合起来就是 O(n)O(n)。

空间复杂度

我们的信息都是对于每一个节点存的，有 nn 个节点，所以是 O(n)O(n)。

实现

通过分开 dfs 来进行预处理和计算每一个节点的答案。
在预处理 dfs 完了之后，需要判一下目前作根的点是否只有一个子节点，如果是，总叶子节点个数要 +1+1。
注意，特判 n=2n=2 的情况，因为两个点都会被计算进总叶子节点，但是只能减去一个。
另外，减少时间消耗小技巧：在判断是否为叶子节点时，不需要算完有多少子节点，大于某个值直接返回就行了，因为不是叶子，这也确保了这个操作是 O(1)O(1) 的。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge
{
	int to,nxt;
} e[500010];
int head[500010],cnt,ans,son,sl[500050],num[500010];
inline void add(int u,int v)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int check(int u,int f)
{
	int sum=0;
	for(int i=head[u];i!=0&&sum<=1;i=e[i].nxt)
	{
		int v=e[i].to;
		if(f!=v) sum++;
	}
	return sum;
}
void dfs1(int u,int f)
{
	num[u]=1;
	sl[u]=0;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v!=f)  
		{
			num[u]++;
			if(!check(v,u)) sl[u]++,son++;
			dfs1(v,u);
		}
	}
}
void dfs2(int u,int f)
{
	ans=max(ans,sl[u]);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v!=f) dfs2(v,u);
	}
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;	
		cnt=ans=son=0;
		for(int i=0;i<=2*n;i++) head[i]=0,e[i]={0,0},num[i]=0,sl[i]=0; 
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			add(u,v);
			add(v,u);
		}									
		if(n==2) {cout<<"0\n";continue;}
		dfs1(1,0);
		if(check(1,0)==1) 
		{
			son++;
			for(int i=head[1];i;i=e[i].nxt) 
			{
				int v=e[i].to;
				if(v!=0) sl[v]++;
			}
		}
		dfs2(1,0);
		cout<<son-ans<<endl;
	}
	return 0;
}
完结撒花！
碎碎念：机房某位大佬看到是树的题就跳了，但是水到我这个蒟蒻都可以过

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...