2023河南萌新联赛第（六）场：河南理工大学
https://ac.nowcoder.com/acm/contest/63602/C
题意
小C喜欢旅游，现在他要去DSH旅游，DSH里有 n n n个城市和 n − 1 n−1 n−1条双向道路（每条道路长度为1），每条道路连接两个城市，并且任意两个城市都可以通过这些的道路互相到达。现在小C要使用魔法指定传送到DSH里的一个城市，作为他旅游的出发城市，小C旅游遵从以下原则：
- 当小C抵达一个城市的时候，他会去跟当前这个城市相连的城市；
- 他只去他以前没有去过的城市；
- 在每个城市，小C以相同的概率移动去上述符合要求的城市；
当没有这样的城市（可走）时，小C就停下了。
由于小C太喜欢DSH了，所以请你告诉小C，在他可以指定传送出发城市的情况下，他的旅游路径的期望最大值是多少。文章来源：https://www.toymoban.com/news/detail-657544.html
解题思路
先确定
1
1
1为根节点，设
d
p
x
dp_x
dpx表示以
x
x
x为根的子树内走过节点个数的期望值，则
d
p
x
=
1
+
1
∣
s
o
n
x
∣
∑
s
∈
s
o
n
x
d
p
s
dp_x=1+\frac{1}{|son_x|}\sum_{s\in son_x}dp_s
dpx=1+∣sonx∣1∑s∈sonxdps，求出后，设
f
x
f_x
fx表示以
x
x
x为出发点，经过节点个数的期望值，显然
f
1
=
d
p
1
f_1=dp_1
f1=dp1，可以用换根
d
p
dp
dp，
O
(
n
)
O(n)
O(n)求出
{
f
}
\{f\}
{f}，对于
f
x
f_x
fx，其值包括其原来的子树的贡献和原来的父亲
f
a
fa
fa的贡献。首先考虑子树，贡献为
1
∣
s
o
n
x
+
1
∣
∑
s
∈
s
o
n
x
f
s
\dfrac{1}{|son_x+1|}\sum_{s\in son_x}f_s
∣sonx+1∣1∑s∈sonxfs，可以发现
∑
s
∈
s
o
n
x
f
s
=
(
d
p
x
−
1
)
×
∣
s
o
n
x
∣
\sum_{s\in son_x}f_s=(dp_x-1)\times|son_x|
∑s∈sonxfs=(dpx−1)×∣sonx∣，所以为
∣
s
o
n
x
∣
∣
s
o
n
x
+
1
∣
(
d
p
x
−
1
)
\dfrac{|son_x|}{|son_x+1|}(dp_x-1)
∣sonx+1∣∣sonx∣(dpx−1)。对于
f
a
fa
fa的贡献，包括以
f
a
fa
fa为根的树的期望减去以
x
x
x为儿子的贡献，为
v
e
c
f
a
.
s
i
z
e
(
)
×
f
f
a
−
d
p
x
−
1
v
e
c
f
a
.
s
i
z
e
(
)
−
1
×
1
∣
s
o
n
x
∣
+
1
\dfrac{vec_{fa}.size()\times f_{fa}-dp_x-1}{vec_{fa}.size()-1}\times\dfrac{1}{|son_x|+1}
vecfa.size()−1vecfa.size()×ffa−dpx−1×∣sonx∣+11（之所以用
v
e
c
f
a
.
s
i
z
e
(
)
vec_{fa}.size()
vecfa.size()是避免
f
a
=
1
fa=1
fa=1时再分类讨论），加上其本身，整理可得：
f
x
=
1
∣
s
o
n
x
∣
+
1
(
(
d
p
x
−
1
)
×
∣
s
o
n
x
+
1
∣
+
v
e
c
f
a
.
s
i
z
e
(
)
×
f
f
a
−
d
a
x
−
1
v
e
c
f
a
.
s
i
z
e
(
)
−
1
)
+
1
f_x=\dfrac{1}{|son_x|+1}((dp_x-1)\times|son_x+1|+\dfrac{vec_{fa}.size()\times f_{fa}-da_x-1}{vec_{fa}.size()-1})+1
fx=∣sonx∣+11((dpx−1)×∣sonx+1∣+vecfa.size()−1vecfa.size()×ffa−dax−1)+1
记得
g
g
g表示的是节点数，答案要求路径长，要将最大值减一。文章来源地址https://www.toymoban.com/news/detail-657544.html
代码
#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);
}
到了这里，关于2023河南萌新联赛第（六）场：河南理工大学-C 旅游的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
