codeforces 697D Puzzles (树形dp 期望推荐)

56 阅读 0 评论 37 点赞

我是靠谱客的博主敏感黑米，最近开发中收集的这篇文章主要介绍codeforces 697D Puzzles (树形dp 期望推荐)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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.

$\text{[math]}$

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 ≤ 10⁵) — the number of cities in USC.

The second line contains n - 1 integers p₂, p₃, ..., p_n (1 ≤ p_i < i), where p_i is the number of the parent city of city number i in the tree, meaning there is a road between cities numbered p_i 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

题目链接：http://codeforces.com/problemset/problem/697/D

题目大意：给一棵树，求从根按等概率随机的DFS遍历时，每个结点被访问时的时间戳的期望值

题目分析：设dp[i]为从根到点i时间戳的期望值，对于结点v，设其父结点为u，则到v的期望值分为两部分，一部分是dp[u]+1即从父亲一步走过来，一部分是先去遍历父亲的其他子树，设父亲共有k个子树，则每棵子树被访问的概率为1/k，且所有的访问顺序的个数为k!，设某另一个子树w，则在所有访问序列中v在w前和w在v前的各占1/2，同理u的所有非v子树都拥有这个性质，根据伪代码可以发现回溯的时间不算，因此先w后v时dp[v]要加size[w]/2，其余子树同理，故得到dp[v]=dp[u]+1+size[u的所有非v子树]/2，size数组显然可以用一个DFS预处理一下，然后不难得到size[u的所有非v子树] = sz[u] - sz[v] - 1

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 1e5 + 5;
struct EDGE {
    int to, nxt;
}e[MAX];
int n, sz[MAX];
int head[MAX], cnt;
double dp[MAX];

void Init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void Add(int u, int v) {
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt ++;
}

void getSise(int u, int fa) {
    sz[u] = 1;
    for (int i = head[u]; i != -1; i = e[i].nxt) {
        int v = e[i].to;
        if (v != fa) {
            getSise(v, u);
            sz[u] += sz[v];
        }
    }
}

void DFS(int u, int fa) {
    for (int i = head[u]; i != -1; i = e[i].nxt) {
        int v = e[i].to;
        if (v != fa) {
            dp[v] = dp[u] + 1.0 + (sz[u] - sz[v] - 1) / 2.0;
            DFS(v, u);
        }
    }
}

int main() {
    Init();
    scanf("%d", &n);
    int u;
    for (int v = 2; v <= n; v ++) {
        scanf("%d", &u);
        Add(u, v);
    }
    getSise(1, -1);
    dp[1] = 1.0;
    DFS(1, -1);
    for (int i = 1; i <= n; i ++) {
        printf("%.6f ", dp[i]);
    }
    printf("n");
}