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

题意：

给你一棵树，求出最小的连接方法使得切去任意一条边能从任何点回到根

题解：

刚开始想的是使叶子结点连通，但是会有很多麻烦的情况，后来问别人才知道需要加入根节点，然后就像这个图一样，使得中间的和边上的连就可以了，需要dfs的时候插入。这会让所有根的子树相连，如果根只有一个子树，那么根也在vector里面。

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
int root;
const int N=1e5+5;
struct node
{
    int to,next;
}e[N<<1];
int cnt,head[N];
void add(int x,int y)
{
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
vector<int>lev;
int vis[N];
void dfs(int x,int f)
{
    if(vis[x]==1)
        lev.push_back(x);
    for(int i=head[x];~i;i=e[i].next)
    {
        int ne=e[i].to;
        if(ne==f)
            continue;
        dfs(ne,x);
    }
}
int main()
{
    int n;
    int numroot=0;
    scanf("%d%d",&n,&root);
    memset(head,-1,sizeof(head));
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
        vis[x]++,vis[y]++;
    }
    dfs(root,-1);
    printf("%d\n",(lev.size()+1)/2);
    for(int i=0;i<lev.size()/2;i++)
        printf("%d %d\n",lev[i+lev.size()/2],lev[i]);
    if(int(lev.size())%2)
        printf("%d %d\n",lev[lev.size()-1],lev[0]);
    return 0;
}