如何做网站描述,南昌建网站那家好,遵义网络科技公司,利用社交网站做淘宝客2023河南萌新联赛第#xff08;六#xff09;场#xff1a;河南理工大学 C - 旅游 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K Special Judge, 64bit IO Format: %lld 题目描述
小C喜欢旅游#xf…2023河南萌新联赛第六场河南理工大学 C - 旅游 时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K Special Judge, 64bit IO Format: %lld 题目描述
小C喜欢旅游现在他要去DSH旅游DSH里有nnn个城市和 n − 1 n-1 n−1 条双向道路每条道路长度为1每条道路连接两个城市并且任意两个城市都可以通过这些的道路互相到达。现在小C要使用魔法指定传送到DSH里的一个城市作为他旅游的出发城市小C旅游遵从以下原则
当小C抵达一个城市的时候他会去跟当前这个城市相连的城市他只去他以前没有去过的城市在每个城市小C以相同的概率移动去上述符合要求的城市当没有这样的城市可走时小C就停下了。
由于小C太喜欢DSH了所以请你告诉小C在他可以指定传送出发城市的情况下他的旅游路径的期望最大值是多少。
输入描述:
第1行一个整数 n ( 1 ≤ n ≤ 100000 ) n(1\leq n \leq 100000) n(1≤n≤100000)表示DSH有 n n n个城市 接下来 n − 1 n-1 n−1行每行包含两个整数 a a a和 b ( 1 ≤ a , b ≤ n ) b (1 \leq a, b \leq n) b(1≤a,b≤n)表示城市 a a a和城市 b b b之间有一条双向道路。
输出描述:
输出一个数表示这次旅游期望可以达到的最大值保留三位小数。
示例1
输入
4
1 2
1 3
2 4输出
3.000说明 如上图 如果初始传送至城市3那么他的旅游路径是 ( 3 , 1 , 2 , 4 ) (3,1,2,4) (3,1,2,4)总距离为3期望为3 如果初始传送至城市1那么他的旅游路径可以是 ( 1 , 2 , 4 ) (1,2,4) (1,2,4)总距离为2也可以是 ( 1 , 3 ) (1,3) (1,3)总距离为1所以期望是1.5 如果初始传送至城市2那么他的旅游路径可以是 ( 2 , 4 ) (2,4) (2,4)总距离是1也可以是 ( 2 , 1 , 3 ) (2,1,3) (2,1,3)总距离是2所以期望是1.5 如果初始传送至城市4那么他的旅游路径是 ( 4 , 2 , 1 , 3 ) (4,2,1,3) (4,2,1,3)总距离为3期望为3。 所以最大期望是3。 示例2
输入
7
1 4
1 2
4 5
4 3
2 7
2 6输出
3.000import java.io.*;
import java.util.ArrayList;public class Main {static int N 100010;static ArrayListInteger[] 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();}
}
