专栏文章

题解：P13555 【MX-X15-T2】系绳绳

AACcepted917
P13555题解参与者 1已保存评论 0

文章操作

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

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

题解：P13555 【MX-X15-T2】系绳绳

题目传送门
非常有意思的一道题，赛时想了半小时。

前置知识

度数

对于边为无向的图/树，一个节点的度数的定义为连接这个节点的边数。
如上图，11 号节点的度数为 22，44 号节点的度数为 11。

分析

简化一下题意，对于每次操作，选一个编号为 kk 的节点作为树的根节点，每个节点都用“绳子”连接它的祖先节点。求最小的操作次数，使得每两个节点都有绳子连接。
先考虑特殊性质。

特殊性质#1：每个节点的度数都不超过 22

如果每个节点的度数都不超过 22，那么这棵树是线性的，如下图。
不难发现，选择头/尾节点任意其一（即图中读数为 11 的 11 号节点和 55 号节点）进行操作，就能让每两个节点都有绳子连接（图中红色线为“绳子”）。
所以输出 11 即可。

特殊性质#2：存在一个节点的度数为 n−1n−1

显然，必有 n−1n-1 个度数为 11 的叶子节点，选择这些叶子中任意 n−2n-2 个进行操作，即可满足要求，所以输出 n−2n-2 即可。
读者如果不懂，可以自行按照上图操作一下（qwq）。

最终结论

通过上述对于特殊性质的探究，我们发现，最小的操作次数都为叶子节点的个数减 11。
所以：
可以证明，如果叶子节点（即度数为 11 的节点）的个数为 kk，则答案为 k−1k-1。

坑

统计每组数据的节点度数之前，统计度数的数组要初始化。
当输入的 nn 为 11 时，要特判，输出 00。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const unsigned long long N=1e5+5;
typedef long long ll;
int x,y,z,c,a,n,m,k,t,d[N],f1,f2;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		memset(d,0,sizeof(d));//记得初始化qwq
		cin>>n;
		if(n==1){//特判，n为1
			cout<<0<<'\n';
			continue;
		}
		for(register int i=1;i<n;i++){
			cin>>x>>y;
			d[x]++;//统计每个点的度数
			d[y]++;//同上
		}
		c=0;//计数器
		for(register int i=1;i<=n;i++){
			//cout<<d[i]<<' ';
			if(d[i]==1)c++;//统计度数为1的节点个数
		}
		cout<<c-1<<'\n';
	}
	return 0;
}

评论

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

正在加载评论...