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

发表评论

邮箱地址不会被公开。 必填项已用*标注