Kingpin Escape(dfs 树)

题目描述
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?

输入
• 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.

输出
The output consists of:
• An integer m, the least number of escape routes you need to add to make the network safe again.
• 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.

样例输入
4 0
0 1
0 2
0 3

样例输出
2
3 2
3 1

思路
将所有叶节点自左右向中间链接，当根节点也只有一个子树时，同样也将其联通，这样就可以使所有节点在断一条边时全部联通

代码实现

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+5;
struct tree
{
    int index,to;
}tr[N<<1];
int head[N];
int cnt,n,root;
int vis[N];
vector<int> getn;
void add(int u,int v)
{
    tr[cnt].index=v;
    tr[cnt].to=head[u];
    head[u]=cnt++;
}
void dfs(int x,int y)
{
    if(vis[x]==1) getn.push_back(x);
    for(int i=head[x];~i;i=tr[i].to)
    {
        int next=tr[i].index;
        if(next==y) continue;
        dfs(next,x);
    }
}
int main()
{
    scanf("%d%d",&n,&root);
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
        vis[u]++,vis[v]++;
    }
    dfs(root,-1);
    printf("%d\n",(getn.size()+1)/2);
    for(int i=0;i<getn.size()/2;i++)
    {
        printf("%d %d\n",getn[i+getn.size()/2],getn[i]);
    }
    if(int(getn.size())&1)
    {
         printf("%d %d\n",getn[getn.size()-1],getn[0]);
    }
    return 0;
}