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;
}