（思维/分类）Useful Decomposition CodeForces – 981C

传送门：https://vjudge.net/problem/CodeForces-981C
* **大意：** 给了一棵树，让把这棵树拆成多条链，任意两条链必须要有交点，如果可以的话就输出链的个数以及每条链的两个端点，否则就输出No。
* **思路：** 只有两种情况输出Yes，一种是一条链，即只有两个点出（入）度为1，其余皆为2；另一种是有h个点出（入）度为1，而只有一个点出（入）度为h，且如果无第二个出（入）度大于2的点，那么最大出（入）度点即为所有链的起（终）点。
另外，此题是无向的，无需记录链上点的先后顺序。

代码：

#include <iostream>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
#include<set>
#include<vector>
#include<assert.h>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

const int maxn = 1e5+5;

int a[maxn];
int b[maxn];

int main(){
	int n;
	int x,y;
	memset(a,0,sizeof(a));
	scanf("%d", &n);
	rep(i,1,n-1){
		scanf("%d%d", &x,&y);
		a[x]++;
		a[y]++;
	}
	int sign;
	int s1 = 0,s2 = 0,m = 0;
	rep(i,1,n){
		if(a[i] == 1){
			s1++;
			b[s1] = i;
		}
		if(a[i]>m){
			 m = a[i];
			 sign = i;
		}
		if(a[i] > 2) s2++;
	}
	if(s2>1){
		printf("No");
	}else if(s1 == 2){
		printf("Yes\n%d\n", 1);
		printf("%d %d",b[1],b[2] );
	}else{
		printf("Yes\n%d\n",m);
		rep(i,1,s1){
			printf("%d %d",sign,b[i]);
			if(i != s1) printf("\n");
		}
	}
	
	return 0;
}