Cover the Tree

题目描述

输入描述:

输出描述:

示例1

输入

5
1 2
1 3
2 4
2 5

输出

2
2 3
4 5

说明

题目大意

给定一个k个节点的无根树，求最少的链覆盖树上的所有边。并输出覆盖方式（链的两边的节点编号）(SPJ)。

分析

一看就想到和叶节点有关。由于每个叶节点一定要覆盖到，则若有n个叶节点，则必要n/2向上取整的链才能覆盖到所有叶节点，并且这些链可以同时覆盖其他边。
于是，链的数量就求出来了，重点是覆盖的策略。一开始写的好像可以hack掉

覆盖策略

先用dfs序将每个叶节点编号，然后以ans/2为界，一一对应做链即可。经过长期实验+数百次WA+官方题解易得

代码

#include<bits/stdc++.h>
#define ll long long
#define inf 1<<30
using namespace std;
const int MAXN=2e5+100;
vector<int> vec[MAXN];
int a[MAXN],num;
void dfs(int pos,int fa){
	if(vec[pos].size()==1){
		a[++num]=pos;return;
	}//size==1的就是叶节点，依照此顺序存到数组中
	for(int i=0;i<vec[pos].size();i++){
		int s=vec[pos][i];
		if(s==fa) continue;
		dfs(s,pos);
	}
}
int main()
{
    int k,u,v;
    scanf("%d",&k);
    for(int i=1;i<k;i++){
        scanf("%d%d",&u,&v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    if(k==2){
    	printf("1\n");
    	printf("%d %d\n",u,v);return 0;
	}
    for(int i=1;i<=k;i++)
    	if(vec[i].size()>1){
    		dfs(i,-1);break;
    		//无根树因此需要找一个root做dfs
		}
    printf("%d\n",(num+1)/2);//答案即为叶节点个数一半ceil
    for(int i=1;i<=(num+1)/2;i++){
        int x=a[i],y=a[i+num/2];
        printf("%d %d\n",x,y);
    }//按上述策略输出
}

END