珲春建设局网站,网站建设售前说明书,石家庄建站系统,成都网站制作价格2023河南萌新联赛第#xff08;六#xff09;场#xff1a;河南理工大学
https://ac.nowcoder.com/acm/contest/63602/C 文章目录 2023河南萌新联赛第#xff08;六#xff09;场#xff1a;河南理工大学题意解题思路代码 题意
小C喜欢旅游#xff0c;现在他要去DSH旅…2023河南萌新联赛第六场河南理工大学
https://ac.nowcoder.com/acm/contest/63602/C 文章目录 2023河南萌新联赛第六场河南理工大学题意解题思路代码 题意
小C喜欢旅游现在他要去DSH旅游DSH里有 n n n个城市和 n − 1 n−1 n−1条双向道路每条道路长度为1每条道路连接两个城市并且任意两个城市都可以通过这些的道路互相到达。现在小C要使用魔法指定传送到DSH里的一个城市作为他旅游的出发城市小C旅游遵从以下原则
当小C抵达一个城市的时候他会去跟当前这个城市相连的城市他只去他以前没有去过的城市在每个城市小C以相同的概率移动去上述符合要求的城市
当没有这样的城市可走时小C就停下了。 由于小C太喜欢DSH了所以请你告诉小C在他可以指定传送出发城市的情况下他的旅游路径的期望最大值是多少。
解题思路
先确定 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_x1\frac{1}{|son_x|}\sum_{s\in son_x}dp_s dpx1∣sonx∣1∑s∈sonxdps求出后设 f x f_x fx表示以 x x x为出发点经过节点个数的期望值显然 f 1 d p 1 f_1dp_1 f1dp1可以用换根 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_x1|}\sum_{s\in son_x}f_s ∣sonx1∣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_x1|}(dp_x-1) ∣sonx1∣∣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 fa1 fa1时再分类讨论加上其本身整理可得 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_x1|\dfrac{vec_{fa}.size()\times f_{fa}-da_x-1}{vec_{fa}.size()-1})1 fx∣sonx∣11((dpx−1)×∣sonx1∣vecfa.size()−1vecfa.size()×ffa−dax−1)1 记得 g g g表示的是节点数答案要求路径长要将最大值减一。
代码
#includebits/stdc.h
using namespace std;
const int N1e55;
int n;
double dp[N],f[N],ma;
vectorintve[N];
void dfs1(int u,int fa){int cnt(ve[u].size()-(u!1?1:0));for(auto v:ve[u]){if(vfa)continue;dfs1(v,u);dp[u]1.0/cnt*dp[v];}dp[u]dp[u]1;
}
void dfs2(int u,int fa){mamax(f[u],ma);int sumve[u].size();for(auto v:ve[u]){if(vfa)continue;int cntve[v].size()-1;f[v](1.0*(dp[v]-1)*cnt(sum1?(sum*f[u]-dp[v]-1)/(sum-1):1))/(cnt1)1;dfs2(v,u);}
}
int main(){cinn;for(int i1;in;i){int u,v;cinuv;ve[u].push_back(v);ve[v].push_back(u);}dfs1(1,0);f[1]dp[1];dfs2(1,0);printf(%.3lf,ma-1);
}
