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

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

https://ac.nowcoder.com/acm/contest/63602/C

题意

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

1. 当小C抵达一个城市的时候，他会去跟当前这个城市相连的城市；
2. 他只去他以前没有去过的城市；
3. 在每个城市，小C以相同的概率移动去上述符合要求的城市；

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

解题思路

先确定$1$为根节点，设$d{p}_x$表示以$x$为根的子树内走过节点个数的期望值，则$d{p}_x=1+\frac{1}{|so{n}_x|}{\sum }_{s\in so{n}_x}d{p}_s$，求出后，设$f_x$表示以$x$为出发点，经过节点个数的期望值，显然$f_1=d{p}_1$，可以用换根$dp$，$O(n)$求出 { f } \{f\} {f}，对于$f_x$，其值包括其原来的子树的贡献和原来的父亲$fa$的贡献。首先考虑子树，贡献为$\frac{1}{|so{n}_x+1|}{\sum }_{s\in so{n}_x}{f}_s$，可以发现${\sum }_{s\in so{n}_x}{f}_s=(d{p}_x-1)\times |so{n}_x|$，所以为$\frac{|so{n}_x|}{|so{n}_x+1|}(d{p}_x-1)$。对于$fa$的贡献，包括以$fa$为根的树的期望减去以$x$为儿子的贡献，为$\frac{ve{c}_{fa}.size()\times f_{fa}-d{p}_x-1}{ve{c}_{fa}.size()-1}\times \frac{1}{|so{n}_x|+1}$（之所以用$ve{c}_{fa}.size()$是避免$fa=1$时再分类讨论），加上其本身，整理可得：
$$f_x=\frac{1}{|so{n}_x|+1}((d{p}_x-1)\times |so{n}_x+1|+\frac{ve{c}_{fa}.size()\times f_{fa}-d{a}_x-1}{ve{c}_{fa}.size()-1})+1$$
记得$g$表示的是节点数，答案要求路径长，要将最大值减一。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
double dp[N],f[N],ma;
vector<int>ve[N];
void dfs1(int u,int fa){int cnt=(ve[u].size()-(u!=1?1:0));for(auto v:ve[u]){if(v==fa)continue;dfs1(v,u);dp[u]+=1.0/cnt*dp[v];}dp[u]=dp[u]+1;
}
void dfs2(int u,int fa){ma=max(f[u],ma);int sum=ve[u].size();for(auto v:ve[u]){if(v==fa)continue;int cnt=ve[v].size()-1;f[v]=(1.0*(dp[v]-1)*cnt+(sum>1?(sum*f[u]-dp[v]-1)/(sum-1):1))/(cnt+1)+1;dfs2(v,u);}
}
int main(){cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;ve[u].push_back(v);ve[v].push_back(u);}dfs1(1,0);f[1]=dp[1];dfs2(1,0);printf("%.3lf",ma-1);
}