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;
}