【Codeforces 696B】Puzzles

题目传送门：http://codeforces.com/contest/696/problem/B
官方题解：http://codeforces.com/blog/entry/46031
中文题面：http://blog.csdn.net/oulaline/article/details/51941548
中文题解：http://blog.csdn.net/TRiddle/article/details/51919455#t12

这个题目好神！ 赶紧Mark！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;

int head[N],nxt[N],to[N],n,sz[N],dep[N]; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v){
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

void DFS(int w) {
	sz[w] = 1;
	for (int i=head[w];i;i=nxt[i]) 
		dep[to[i]] = dep[w] + 1, 
		DFS(to[i]), sz[w] += sz[to[i]];
}

int main(){
	n = read(); for (int i=2;i<=n;i++) Add_Edge(read(),i); DFS(1);
	for (int i=1;i<=n;i++) printf("%.1lf ",dep[i]+(n-dep[i]-sz[i])*0.5+1);
	return 0;
}