4657: Puzzles 拼图
内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：5
通过：2
题目描述
巴尼住在南加州大学（查泽美国）。南加州大学有n个城市，编号从1到n和n-1道路。 南加州大学的城市和道路形成了一棵有根的树（巴尼不知道为什么它有根）。树根是城市编号1。因此，如果一个人从城市 1 开始他的旅程，他可以通过沿着道路访问他想要的任何城市。
某个女孩偷走了巴尼的心，巴尼想找到她。他开始在树根中寻找（因为他是巴尼·斯廷森而不是一个随机的人），他使用随机DFS在城市中搜索。该算法的伪代码如下：
如前所述，Barney 将在树根开始他的旅程（相当于调用 dfs（1））。
现在巴尼需要收拾背包，所以他想知道更多关于他即将到来的旅程：对于每个城市，巴尼都想知道starting_time[i]的预期价值。他是琼恩·雪诺的朋友，什么都不知道，这就是他寻求你帮助的原因。
某个女孩偷走了巴尼的心，巴尼想找到她。他开始在树根中寻找（因为他是巴尼·斯廷森而不是一个随机的人），他使用随机DFS在城市中搜索。该算法的伪代码如下：
如前所述，Barney 将在树根开始他的旅程（相当于调用 dfs（1））。
现在巴尼需要收拾背包，所以他想知道更多关于他即将到来的旅程：对于每个城市，巴尼都想知道starting_time[i]的预期价值。他是琼恩·雪诺的朋友，什么都不知道，这就是他寻求你帮助的原因。
let starting_time be an array of length n current_time = 0 dfs(v): current_time = current_time + 1 starting_time[v] = current_time shuffle children[v] randomly (each permutation with equal possibility) // children[v] is vector of children cities of city v for u in children[v]: dfs(u)
Barney lives in country USC (United States of Charzeh). USC has n cities numbered from 1 through n and n-1 roads between them. Cities and roads of USC form a rooted tree (Barney's not sure why it is rooted). Root of the tree is the city number 1. Thus if one will start his journey from city 1, he can visit any city he wants by following roads.
Some girl has stolen Barney's heart, and Barney wants to find her. He starts looking for in the root of the tree and (since he is Barney Stinson not a random guy), he uses a random DFS to search in the cities. A pseudo code of this algorithm is as follows:
Now Barney needs to pack a backpack and so he wants to know more about his upcoming journey: for every city i, Barney wants to know the expected value of starting_time[i]. He's a friend of Jon Snow and knows nothing, that's why he asked for your help.
Some girl has stolen Barney's heart, and Barney wants to find her. He starts looking for in the root of the tree and (since he is Barney Stinson not a random guy), he uses a random DFS to search in the cities. A pseudo code of this algorithm is as follows: let starting_time be an array of length n current_time = 0 dfs(v): current_time = current_time + 1 starting_time[v] = current_time shuffle children[v] randomly (each permutation with equal possibility) // children[v] is vector of children cities of city v for u in children[v]: dfs(u)As told before, Barney will start his journey in the root of the tree (equivalent to call dfs(1)).
Now Barney needs to pack a backpack and so he wants to know more about his upcoming journey: for every city i, Barney wants to know the expected value of starting_time[i]. He's a friend of Jon Snow and knows nothing, that's why he asked for your help.
Input
The first line of input contains a single integer n (1≤n≤105)− the number of cities in USC. The second line contains n-1 integers p2,p3,...,pn (1≤pi<i), where pi is the number of the parent city of city number i in the tree, meaning there is a road between cities numbered pi and i in USC.
Output
In the first and only line of output print n numbers, where i-th number is the expected value of starting_time[i]. Your answer for each city will be considered correct if its absolute or relative error does not exceed 10-6.
Examples
Input
7 1 2 1 1 4 4
Output
1.0 4.0 5.0 3.5 4.5 5.0 5.0
Input
12 1 1 2 2 4 4 3 3 1 10 8
Output
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0
输入格式
输入的第一行包含单个整数 n (1≤N≤105）− 南加州大学的城市数量。
第二行包含 n-1 个整数p2，p3,...,pn (1≤pi<i），其中p我是树中城市编号 i 的父城市编号，表示城市之间有一条道路编号p我和我在南加州大学。
第二行包含 n-1 个整数p2，p3,...,pn (1≤pi<i），其中p我是树中城市编号 i 的父城市编号，表示城市之间有一条道路编号p我和我在南加州大学。
输出格式
输出
在输出的第一行也是唯一一行中打印 n 个数字，其中第 i 个数字是 starting_time[i] 的期望值。如果每个城市的绝对或相对误差不超过10-6.
例子
输入
7 1 2 1 1 4 4
输出
1.0 4.0 5.0 3.5 4.5 5.0 5.0
输入
12 1 1 2 2 4 4 3 3 1 10 8
输出
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0
输入样例 复制
7
1 2 1 1 4 4输出样例 复制
1.0 4.0 5.0 3.5 4.5 5.0 5.0