2023河南萌新联赛第（六）场：河南理工大学 C - 旅游

2023河南萌新联赛第（六）场：河南理工大学 C - 旅游

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

小C喜欢旅游，现在他要去DSH旅游，DSH里有nnn个城市和 $n-1$ 条双向道路（每条道路长度为1），每条道路连接两个城市，并且任意两个城市都可以通过这些的道路互相到达。现在小C要使用魔法指定传送到DSH里的一个城市，作为他旅游的出发城市，小C旅游遵从以下原则：

1. ​当小C抵达一个城市的时候，他会去跟当前这个城市相连的城市；
2. ​他只去他以前没有去过的城市；
3. ​在每个城市，小C以相同的概率移动去上述符合要求的城市；
4. ​当没有这样的城市（可走）时，小C就停下了。

​ 由于小C太喜欢DSH了，所以请你告诉小C，在他可以指定传送出发城市的情况下，他的旅游路径的期望最大值是多少。

输入描述:

第1行一个整数$n(1\le n\le 100000)$，表示DSH有$n$个城市；
接下来$n-1$行，每行包含两个整数$a$和$b(1\le a,b\le n)$，表示城市$a$和城市$b$之间有一条双向道路。

输出描述:

输出一个数，表示这次旅游期望可以达到的最大值，保留三位小数。

示例1

输入

4
1 2
1 3
2 4

输出

3.000

说明

如上图：
如果初始传送至城市3，那么他的旅游路径是$(3,1,2,4)$，总距离为3，期望为3；
如果初始传送至城市1，那么他的旅游路径可以是$(1,2,4)$，总距离为2，也可以是$(1,3)$，总距离为1，所以期望是1.5；
如果初始传送至城市2，那么他的旅游路径可以是$(2,4)$，总距离是1，也可以是$(2,1,3)$，总距离是2，所以期望是1.5；
如果初始传送至城市4，那么他的旅游路径是$(4,2,1,3)$，总距离为3，期望为3。
所以最大期望是3。

示例2

输入

7
1 4
1 2
4 5
4 3
2 7
2 6

输出

3.000

import java.io.*;
import java.util.ArrayList;public class Main {static int N = 100010;static ArrayList<Integer>[] adj = new ArrayList[N];static double[] downsum = new double[N];static double[] downavg = new double[N];static double[] upsum = new double[N];static double[] upavg = new double[N];public static void dfs1(int u, int fa) {for (int v : adj[u]) {if (v == fa) continue;dfs1(v, u);downsum[u] += downavg[v];}if (adj[u].size() == 1) downavg[u] = 0;else downavg[u] = downsum[u] / (adj[u].size() - (fa != 0 ? 1 : 0)) + 1;}public static void dfs2(int u, int fa) {for (int v : adj[u]) {if (v == fa) continue;upsum[v] = upavg[u] + downsum[u] - downavg[v];upavg[v] = upsum[v] / (adj[u].size() - 1) + 1;dfs2(v, u);}}public static void main(String[] args) throws IOException {BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));int n = Integer.parseInt(bf.readLine());if (n == 1) {bw.write("0.000\n");} else if (n == 2) {bw.write("1.000\n");} else {for (int i = 1; i <= 100000; i++) adj[i] = new ArrayList<>();for (int i = 1; i <= n - 1; i++) {String[] str = bf.readLine().split(" ");int u = Integer.parseInt(str[0]);int v = Integer.parseInt(str[1]);adj[u].add(v);adj[v].add(u);}int root = 1;while (adj[root].size() == 1) root++;dfs1(root, 0);dfs2(root, 0);double res = 0;for (int i = 1; i <= n; i++) {res = Math.max(res, 1 + (upavg[i] + downsum[i]) / adj[i].size());}bw.write(String.format("%.3f\n", res));}bw.close();}
}