CodeForce 280 C Game on Tree--樹形dpは期待を求めます。

1502 ワード

http://codeforces.com/problemset/problem/280/C
/*
	codeforce game of tree
	     ,          ,              
	         
	                
*/

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#define CLR(c,v) (memset(c,v,sizeof(c)))
using namespace std;

const int inf = -(1<<30);
const int INF =  (1<<30);
const int M   = 1e2 + 10;
const double eps =  1e-8;

template <typename _T>
_T Max(_T a , _T b){
	return (a>b)?(a):(b);
}
template <typename _T>
_T Max(_T a , _T b, _T c){
	return (a>Max(b,c))?(a):(Max(b,c));
}
template <typename _T>
_T Min(_T a , _T b){
	return (a<b)?(a):(b);
}
template <typename _T>
_T Min(_T a , _T b, _T c){
	return (a<Min(b,c))?(a):(Min(b,c));
}


const int M      =  1e5 +10;

vector <int > t[M];
double dp[M];
bool vis[M];

double dfs(int cur, int depth){
	dp[cur] = 1.0 / depth;
	vis[cur] = true;
	for(int i = 0 , size = t[cur].size() ; i < size ; i++){
		int child = t[cur][i];
		if(vis[child])continue;
		dp[cur] += dfs(child , depth + 1);
	}
	return dp[cur];
}

int main(){

	int n;
	while(cin >> n){
		for(int i = 1 ; i < n ; i++){
			int a,b;
			scanf("%d%d",&a , &b);
			//t[Min(a,b)].push_back(Max(a,b));
			t[a].push_back(b);
			t[b].push_back(a);
		}
		printf("%.6f
" , dfs(1,1)); for(int i = 0 ; i <= n ; i++){ t[i].clear(); } memset(vis,0,sizeof(vis)); } return 0; }