Kingpin Escape Gym - 102007K

K Kingpin Escape Time limit: 2s
You are the kingpin of a large network of criminal hackers.
Legend has it there has never been a richer criminal
than you. Not just because you are the smartest, but also
because you are the stingiest.
The police have been after you for years, but they have
never been able to catch you thanks to your great set
of escape routes. Whenever they want to catch you in
one of your many hideouts, you quickly get away through
your network of tunnels, back-alleys and speakeasies. Your
routes are set up so that from every hideout you have in the city you can get to any other
hideout by following only your secret passageways. Furthermore, because you are such a
penny-pincher, your network is the smallest possible: from every hideout to every other hideout
there is precisely one route through the network, no more and no fewer.
Yesterday, your mole in the police force has informed you of an unfortunate fact: the police
are on to you! They have gotten wind of your secret network, and will attempt to catch you.
They are planning to block some of your escape routes, and catch you in the act. They will
start blocking your secret passageways one by one, until you have nowhere left to go.
Fortunately, your headquarters are absolutely safe. If you can just get there, you are always
fine. Furthermore, your mole in the police force can inform you immediately as soon as the
police start blocking passageways, so that they only have time to block one of them before
you get notified. If you get back to your headquarters before they block any more routes,
you’re safe.
You want to add some passageways to the network so that whenever at most one of them is
blocked, you can still get to your headquarters from any other hideout. Since the news has
not changed your frugality, you want to extend your network as cheaply as possible. Can you
figure out the least number of passageways you need to add, and which ones you need?
Input
• The input starts with two integers 2 ≤ n ≤ 105
, the number of hideouts in the network,
and 0 ≤ h < n, the location of your headquarters.
• Then follow n − 1 lines, each with two integers 0 ≤ a, b < n, signifying that there is an
escape route between location a and location b.
Output
The output consists of:
• An integer m, the least number of escape routes you need to add to make the network
safe again.
22 Problem K: Kingpin Escape
• Then, m lines with two integers 0 ≤ a, b < n each, the hideouts between which one of
the escape routes has to be added.
In case there are multiple solutions, any of them will be accepted.
Sample Input 1 Sample Output 1
4 0
0 1
0 2
0 3
2
3 2
3 1
Sample Input 2 Sample Output 2
6 0
0 1
0 2
0 3
1 4
1 5
2
3 5
2 4
 题意：给你一颗树，问至少要添加几条边，使在断了一条边之后，任何一个点都可以到根节点

思路：只要每个度数为1的点都与离自己比较远的点链接就好了，具体来说，就是把所有度数为1的的按dfs序存到数组里，设有x个度数为1的点，那么前x/2的点中，第i个点和x/2+i的点链接，如果最后剩下一个，那么它和第一个度数为1的点链接

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#define eps 1e-8
#include<queue>
using namespace std;
#define maxn 405000
int head[maxn],s,cnt,a[maxn],d[maxn];
struct Edge
{
    int to,next;
} edge[maxn];
void addedge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void init()
{
    memset(head,-1,sizeof(head));
    cnt++;
    s=0;
    memset(d,0,sizeof(d));
}
void dfs(int u,int fa)
{
    if(d[u]==1)
    {
        a[++s]=u;
    }
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;

        dfs(v,u);
    }
}
int main()
{
    int n,h;
    while(scanf("%d %d",&n,&h)!=EOF)
    {
        init();
        for(int i=1; i<=n-1; i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            addedge(x,y);
            addedge(y,x);
            d[y]++;d[x]++;
        }
        dfs(h,-1);
        printf("%d\n",(s+1)/2);
        for(int i=1;i<=s/2;i++)
        {
            printf("%d %d\n",a[i],a[s/2+i]);
        }
        if(s%2==1)
        {
            printf("%d %d\n",a[1],a[s]);
        }
    }
}