codeforces 1066B（树）

dejavu1zz

发布于 2020-10-23 15:22:05

4160

发布于 2020-10-23 15:22:05

文章被收录于专栏：奇妙的算法世界

题意描述

Ramesses knows a lot about problems involving trees (undirected connected graphs without cycles)!

He created a new useful tree decomposition, but he does not know how to construct it, so he asked you for help!

The decomposition is the splitting the edges of the tree in some simple paths in such a way that each two paths have at least one common vertex. Each edge of the tree should be in exactly one path.

Help Remesses, find such a decomposition of the tree or derermine that there is no such decomposition.

给一棵树，问可不可以讲树分解为链，任意两条链至少有一个交点

思路

通过观察发现，如果树本身是一条链，此时满足条件，直接输出树的根节点和尾结点即可。如果树是菊花图，即存在一个结点，与其他结点都联通，此时也满足条件，将各个链输出即可。如果有两个以上的度数为2的点，则无法分解。所以我们只需要统计每个点的度数，最后判断即可。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=3*1e5+10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int n;
int deg[N];
vector<int> node,leaves;
void solve(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y;cin>>x>>y;
        deg[x]++;deg[y]++;
    }
    for(int i=1;i<=n;i++){
        if(deg[i]==1) leaves.push_back(i);
        else if(deg[i]>2) node.push_back(i);
    }
    if(node.size()>=2){
        cout<<"No"<<endl;
        return;
    }
    cout<<"Yes"<<endl;
    if(!node.size()){
        cout<<1<<endl;
        cout<<leaves[0]<<' '<<leaves[1]<<endl;
    }else{
        cout<<leaves.size()<<endl;
        for(int i=0;i<leaves.size();i++) cout<<node[0]<<' '<<leaves[i]<<endl;
    }
}
int main(){
    IOS;
    solve();
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/14 ，如有侵权请联系 cloudcommunity@tencent.com 删除

each