K Search For Mafuyu

[题目链接](https://pintia.cn/problem-sets/1459829212832296960/problems/1459829264400629770)

Mafuyu has hidden in Sekai, and Kanade is searching for her.

In Sekai, there is nothing but a lot of rooms. There are **n** rooms in Sekai, numbered from **1** to **n**. Besides, **n****−****1** pairs of rooms are directly connected by corridors, such that it is possible to move from one room to any other one, using one or more corridors. In other words, rooms in Sekai form a tree.

Kanade is at room **1**, and she knows that Mafuyu may hide in any room except room **1**, with uniform probability. In one second, Kanade can move to a room adjacent to the room she is currently in. Once Kanade is in the same room with Mafuyu, she immediately finds her. What is the minimum expected time for Kanade to find Mafuyu, if Kanade is taking the optimal strategy?

### Input

The first line contains an integer **t** (**1****≤****t****≤****1****000**) --- the number of test cases.

The first line in each test case contains an integer **n** (**2****≤****n****≤****100**) --- the number of rooms.

Each of the following **n****−****1** lines contains two integers **a****i******, **b****i****** (**1****≤****a****i********,****b****i********≤****n**) --- the rooms connected by the **i**-th corridor. It is guaranteed that it is possible to move from one room to any other one, using one or more corridors.

### Output

Output **t** real numbers. For each test case, output the minimum expected time. Your answer is considered correct if the absolute or relative error is less than **1****0****−****9**.

### Sample Input

```in
4
2
1 2
5
1 2
2 3
3 4
1 5
7
1 2
1 3
2 4
2 5
3 6
3 7
10
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
9 10
```

### Output

```out
1.0000000000
3.2500000000
5.3333333333
8.0000000000
```

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
int T;
int n;
vector<pair<int,int> > v[N];
int vis[N],dp[N];
int step=0,sum=0;
void dfs1(int p)
{
    vis[p]=1;
    sum+=step;
    for(int i=0;i<v[p].size();i++)
    {
        int to = v[p][i].second;
        if(vis[to]==0)
        {
            step++;
            dfs1(to);
        }
    }
    step++;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) {v[i].clear();vis[i]=0;}
        step=0;sum=0;
        for(int i=1;i<n;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            v[l].push_back(make_pair(0,r));
            v[r].push_back(make_pair(0,l));
        }
        dfs1(1);
        printf("%.10f\n",(double)sum/(double)(n-1));
    }
}
```

will us

K Search For Mafuyu

评论已关闭

分类

标签

归档

其它