#1858. 长野原龙势流星群

    ID: 1858 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>CTT赛事:contest1822来源:qoj.ac数据:公开样例图论深搜

长野原龙势流星群

长野原龙势流星群

题目描述

标题: 长野原龙势流星群 - Problem - QOJ.ac

#9532. 长野原龙势流星群

Statistics

The problem was used in the following contests:

题目描述

Naganohara Yoimiya 给了你一棵 n 个节点的有根树,1 号节点是根节点,每个点有点权 wi。

你需要对每个点 u 找到一个以 u 为根的非空连通块,并最大化这个连通块内所有点的点权的平均值。

对每个点 u 输出这个最大的平均值。

输入格式

第一行一个正整数 n。

接下来一行 n−1 个正整数 p2,p3,⋯,pn,pi 表示 i 的父节点的编号,保证 pi<i。

接下来一行 n 个正整数 w1,w2,⋯,wn。

输出格式

输出 n 行,第 i 行输出一个实数表示以节点 i 为根的连通块内点权平均值的最大值。

如果你的答案和标准答案的相对误差或绝对误差不超过 10−6 则视为正确。

样例 1 输入

6
1 2 2 1 4
3 1 5 6 6 7

样例 1 输出

4.6666666667
4.7500000000
5.0000000000
6.5000000000
6.0000000000
7.0000000000

测试点约束

对于所有数据,1≤n≤2×105,1≤wi≤109。

  • Subtask 1(10 分):1≤n≤2000。
  • Subtask 2(10 分):pi=⌊i/2⌋。
  • Subtask 3(40 分):1≤n≤50000。
  • Subtask 4(40 分):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6
1 2 2 1 4
3 1 5 6 6 7
4.6666666667
4.7500000000
5.0000000000
6.5000000000
6.0000000000
7.0000000000