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

这篇具有很好参考价值的文章主要介绍了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旅游遵从以下原则：

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

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

输入描述:

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

输出描述:

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

示例1

输入

输出

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

输入

输出

3.000

2023河南萌新联赛第（六）场：河南理工大学 C - 旅游,# Java刷题,# DP动态规划,# 图论,c语言,旅游,java 文章来源地址https://www.toymoban.com/news/detail-672215.html

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