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 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>