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

· · 题解

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

题目传送门

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

前置知识

度数

对于边为无向的图/树，一个节点的度数的定义为连接这个节点的边数。

如上图，1 号节点的度数为 2，4 号节点的度数为 1。

分析

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

先考虑特殊性质。

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

如果每个节点的度数都不超过 2，那么这棵树是线性的，如下图。

不难发现，选择头/尾节点任意其一（即图中读数为 1 的 1 号节点和 5 号节点）进行操作，就能让每两个节点都有绳子连接（图中红色线为“绳子”）。

所以输出 1 即可。

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

显然，必有 n-1 个度数为 1 的叶子节点，选择这些叶子中任意 n-2 个进行操作，即可满足要求，所以输出 n-2 即可。

读者如果不懂，可以自行按照上图操作一下（qwq）。

最终结论

通过上述对于特殊性质的探究，我们发现，最小的操作次数都为叶子节点的个数减 1。

所以：

可以证明，如果叶子节点（即度数为 1 的节点）的个数为 k，则答案为 k-1。

坑

统计每组数据的节点度数之前，统计度数的数组要初始化。

当输入的 n 为 1 时，要特判，输出 0。

代码

#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;
}