codeforces 280 C. Game on Tree
题目链接:https://codeforces.com/problemset/problem/280/C
题意:一棵树,每次操作可以将某个节点以及它所有子节点(包括子节点的子节点…)全部染黑,问将整棵树染黑需要次数的期望.
代码:
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+7;
vector<int> g[N];
int de[N];
void dfs(int u,int fa,int d)
{
de[u]=d;
for(auto it:g[u])
{
if(it==fa) continue;
dfs(it,u,d+1);
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].pb(v);
g[v].pb(u);
}
dfs(1,0,1);
double ans=0;
for(int i=1;i<=n;i++) ans+=1./(double)de[i];
printf("%.10lf\n",ans);
}
版权声明:本文为liangsheng_meng原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。