n < = 5 e 5 n<=5e5 n<=5e5 首先你得知道这个题如果是一个序列那就是斜率优化的模板题，维护下凸壳即可。 我们可以想到一个极其暴力的算法： 在树上走一步相当于在凸包上加入一个点，需要先弹栈。 回溯的时候就把弹掉的栈给回退就行了。 这是 O ( n 2 ) O(n^2) O(n2)的，因为凸包的复杂度是均摊的，不支持可持久化和可回退化。 但是栈支持。 所以只是因为凸包的删点次数太多了我们才复杂度退化。 可以用二分删点+可持久化栈的奇妙写法得到 O ( n log n ) O(n\log n) O(nlogn)的复杂度。
A C C o d e \rm AC \ Code AC Code
#include<bits/stdc++.h> #define maxn 500005 #define LL long long using namespace std; int n; LL dep[maxn],c[maxn]; double ans[maxn]; int info[maxn],Prev[maxn],to[maxn],cnt_e; void Node(int u,int v){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v; } int q[maxn]; int cal(int u,int h){ int L=0,R=h,mid; for(;L<R;){ mid = (L+R+1) >> 1; if(mid == 0 || (dep[u]-dep[q[mid-1]])*(c[q[mid]]-c[q[mid-1]])-(dep[q[mid]]-dep[q[mid-1]])*(c[u]-c[q[mid-1]])<0) L=mid; else R=mid-1; } return L; } void dfs(int u,int h){ int t=0; if(h>=0){ t=cal(u,h); ans[u] = 1.0 * (c[q[t]] - c[u]) / (dep[u] - dep[q[t]]); t++; } int tmp = q[t];q[t] = u; for(int i=info[u],v;i;i=Prev[i]) dep[v=to[i]]=dep[u]+1,dfs(v,t); q[t]=tmp; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=2,x;i<=n;i++) scanf("%d",&x),Node(x,i); dfs(1,-1); for(int i=2;i<=n;i++) printf("%.10lf\n",ans[i]); }