Codeforces 981 C. Useful Decomposition

题目：点击打开链接

题意：给定一棵树，要求拆成若干条简单路径，并且这些路径都经过一个公共节点。给出任意一个解决方案，如不存在输出No。也就是说呈发散状。

分析：关键是要找到一个根节点，后来发现度最大的可以作为一个根节点，然后沿着根节点搜索，如果为3则不存在，如果度为2继续搜，如果度为1则表示搜到底了。（所有简单路径都经过一个公共节点，我们倒推回去，就是把公共节点看成根节点，然后从这个节点出发，没有分叉的节点；那么只要先判断分叉节点是不是唯一的，如果唯一，那么把所有路径拆下来就可以啦！！！）

代码：

#pragma comment(linker, "/STACK:102400000,102400000")///
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define eps 1e-10
#define MOD 1000000007
#define PI acos(-1.0)
const int N = 3e5+10;

ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int n,f;
vector<int> e[N];
set<int> st;
int vis[N];

void dfs(int x) {
    vis[x]=1;
    for(int i=0;i<e[x].size();i++) {
        int u=e[x][i];
        if(!vis[u]) {
            if(e[u].size()>2) {
                f=1;return ;
            }else if(e[u].size()==1) {
                st.insert(u);continue;
            }else dfs(u);
        }
    }
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n-1;i++) {
        int u,v;
        cin>>u>>v;
        e[u].pb(v),e[v].pb(u);
    }
    int mx=0,pos;
    for(int i=1;i<=n;i++)
        if(e[i].size()>mx) mx=e[i].size(),pos=i;
    dfs(pos);
    if(f) cout<<"No"<<endl;
    else {
        cout<<"Yes"<<endl;
        cout<<st.size()<<endl;
        for(set<int>::iterator it=st.begin();it!=st.end();it++)
            cout<<pos<<" "<<*it<<endl;
    }
    return 0;
}