Cover the Tree

标程写法：
n<=2时，显然==s/2（s为叶子结点数）

s>=3时，将结点按照dfs序排序，l1,l2,l3...假设s为偶数；

那么对于l1->ls/2+1, l2-> ls/2+2...

假设这条链上的儿子结点所覆盖的区间【l，r】,

如果 r < = s/2 ,那么这条边会被 lr - lr + s/2 覆盖

如果 l > s/2 ,那么这条边会被 lL-s/2 - lL;

否则，根的度数不为1，所以 l ≠ 1或者 r ≠ s 必有一个是满足的;l ≠ 1可以得出，这条边在l 1- l s/2+1; r ≠ s，这条边被 l s/2- ls 覆盖；

s点为奇数时，只需根据叶子结点再接一个节点。。。

我觉得，根据做题经验吧；
我们队写的当时也是这个想法，当然不可能有这么严谨的证明；连蒙带猜吧。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn=210000;
int head[maxn],n,cnt,s=0,tot=0,leaf[maxn],du[maxn];
struct edge{
    int nx,to;
}edge[maxn*2];
void add(int u,int v)
{
    edge[++cnt].nx=head[u];
    edge[cnt].to=v;
    head[u]=cnt;
}
void dfs(int u,int fa)
{
    if(du[u]==1){
        leaf[++tot]=u;
    }
    for(int i=head[u];i;i=edge[i].nx)
    {
        int v=edge[i].to;
        if(v!=fa){
            dfs(v,u);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
        du[u]++,du[v]++;//判断度数，度数为1，则为叶子结点
    }
    int rt=0;
    for(int i=1;i<=n;i++)
        if(du[i]>1) rt=i;//确定根，根据标程的证明，n>3的情况下，根的度数不能为1
    dfs(rt,0);
    int k=0;
    printf("%d\n",(tot+1)/2);
    for(int i=1;2*i<=tot;i++)
    {
        printf("%d %d\n",leaf[i],leaf[i+(tot+1)/2]);//跟据上面的证明，li -li+s/2+1
    }
    if(tot&1) printf("%d %d\n",rt,leaf[(tot+1)/2]);
}