传送门: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; }