题面
题解
发现是斜率的形式，答案的相反数可以看做一条直线的斜率。那么我们要答案最小，斜率最大。维护下凸壳就行了。
考试时写了直接
d
f
s
dfs
dfs+暴力弹栈拿了
80
80
80分（还以为自己是O(n)正解美滋滋）
就是直接存下根到当前点的路径上的凸包，然后回退的时候撤销操作。但这样一个点可能在子树下面被弹出多次。所以最坏情况是
O
(
n
2
)
O(n^2)
O(n2)的（链+菊花）。
考虑怎么实现可回退化栈。可以写倍增（我不会），但是发现可以在凸包上二分到该插入的位置，然后直接存一下被删除的第一个点，然后直接把那个位置设为当前点。回退的时候修改回来就行了。这样每次只改一个点。但是由于要二分，还是
O
(
n
log
n
)
O(n\log n)
O(nlogn)的。
CODE
#include <bits/stdc++.h>
using namespace std
;
typedef long long LL
;
inline void read(int &x
) {
char ch
; while(!isdigit(ch
=getchar()));
for(x
=ch
-'0';isdigit(ch
=getchar());x
=x
*10+ch
-'0');
}
const int MAXN
= 500005;
int n
, x
[MAXN
], y
[MAXN
], fa
[MAXN
], fir
[MAXN
], to
[MAXN
], nxt
[MAXN
], cnt
;
inline void link(int u
, int v
) { to
[++cnt
] = v
; nxt
[cnt
] = fir
[u
]; fir
[u
] = cnt
; }
int q
[MAXN
];
double ans
[MAXN
];
inline LL
Cross(LL a
, LL b
, LL c
, LL d
) { return a
*d
- b
*c
; }
int find(int i
, int r
) {
int l
= 2, mid
, re
= r
+1;
while(l
<= r
) {
mid
= (l
+ r
) >> 1;
if(Cross(x
[i
]-x
[q
[mid
-1]], y
[i
]-y
[q
[mid
-1]], x
[i
]-x
[q
[mid
]], y
[i
]-y
[q
[mid
]]) <= 0) re
= mid
, r
= mid
-1;
else l
= mid
+1;
}
ans
[i
] = (double)(y
[q
[re
-1]]-y
[i
]) / (double)(x
[i
]-x
[q
[re
-1]]);
return re
;
}
void dfs(int u
, int now
) {
x
[u
] = x
[fa
[u
]] + 1;
int pos
= now
? find(u
, now
) : 1, id
= q
[pos
];
q
[pos
] = u
;
for(int i
= fir
[u
]; i
; i
= nxt
[i
])
dfs(to
[i
], pos
);
q
[pos
] = id
;
}
int main
() {
freopen("lost.in", "r", stdin);
freopen("lost.out", "w", stdout);
read(n
);
for(int i
= 1; i
<= n
; ++i
) read(y
[i
]);
for(int i
= 2; i
<= n
; ++i
) read(fa
[i
]), link(fa
[i
], i
);
dfs(1, 0);
for(int i
= 2; i
<= n
; ++i
) printf("%.10f\n", ans
[i
]);
}
