小$w$在天堂看到了一棵世界树。
世界树上有$n$个节点，其中$1$节点为根，每个节点有一个正整数权值$c_i$。
现在小$w$想要对每个节点$u$求出它的祖先$v$中$\frac{c_v-c_u}{dis(u,v)}$的最小值。
第一行一个整数$n$表示节点个数。
第二行$n$个整数，表示每个点的$c_i$。
第三行$n-1$个整数，表示$2$到$n$每个节点的父亲。
$n-1$行，每行一个小数，表示$2$到$n$每个节点的答案，绝对值误差不超过${10}^{-6}$。
样例输入：
8
31516 11930 18726 12481 79550 63015 64275 7608
1 1 2 4 2 4 5
样例输出：
19586.0000000000
12790.0000000000
-551.0000000000
-67069.0000000000
-51085.0000000000
-51794.0000000000
1440.6666666667
对于$20\%$的数据，$n\leqslant 500$。
对于$40\%$的数据，$n\leqslant 5\times {10}^4$。
对于另外$20\%$的数据，保证数据随机。
对于$100\%$的数据，$n\leqslant 5\times {10}^5,c_i\leqslant {10}^9$。
$20\%$算法：
暴力枚举所有父亲，记得$double$就好啦，但是你会意外的发现你得了$50$分，为什么呢？
注意有另外$20\%$的数据为随机数据，也就意味着差不多是$\log n$层的，那么时间复杂度其实趋近于$\Theta(n\log n)$，至于另外的$10$分，那我也不知道啦。
最劣时间复杂度：$\Theta(n^2)$。
最优时间复杂度：$\Theta(n\log n)$。
期望得分：$20$分。
实际得分：$50$分。
$100\%$算法：
来化一下那个式子：$\frac{c_v-c_u}{dis(u,v)}=\frac{c_v-c_u}{dep_u-dep_v}=-\frac{c_u-c_v}{dep_u-dep_v}$。
惊喜的发现这是一个凸包，而且只用维护下凸包就好啦，但是你只能获得$80$分，为什么呢？
因为暴力弹栈最劣情况下是能把程序卡成$\Theta(n^2)$的，类似菊花图，那么怎么办呢？
考虑使用可持久化栈即可。
时间复杂度：$\Theta(n\log n)$。
期望得分：$100$分。
实际得分：$100$分。
$20\%$算法：
#include<bits/stdc++.h>
using namespace std;
int n;
double c[500001];
int fa[500001];
double ans[500001];
int main()
{
memset(ans,127,sizeof(ans));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf",&c[i]);
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
fa[i]=x;
}
for(int i=2;i<=n;i++)
{
int flag=i;
double dis=0.0;
while(flag!=1)
{
flag=fa[flag];
dis++;
ans[i]=min(ans[i],(c[flag]-c[i])/dis);
}
}
for(int i=2;i<=n;i++)
printf("%.8lf\n",ans[i]);
return 0;
}
$100\%$算法：
#include<bits/stdc++.h>
using namespace std;
struct rec
{
int nxt;
int to;
}e[500000];
int head[500001],cnt;
int n;
int c[500001];
int fa[500001][20];
int depth[500001];
int ans[500001];
void add(int x,int y)
{
e[++cnt].nxt=head[x];
e[cnt].to=y;
head[x]=cnt;
}
double calc(int x,int y){return 1.0*(c[y]-c[x])/(depth[x]-depth[y]);}
void dfs(int x)
{
int father=fa[x][0];
for(int i=19;~i;i--)
{
if(fa[father][i]<=1)continue;
if(calc(x,fa[father][i])>=calc(x,fa[fa[father][i]][0]))father=fa[fa[father][i]][0];
}
if(father>1&&calc(x,father)>=calc(x,fa[father][0]))father=fa[father][0];
ans[x]=fa[x][0]=father;
for(int i=1;i<=19;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].nxt)
{
depth[e[i].to]=depth[x]+1;
dfs(e[i].to);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
fa[i][0]=x;
add(x,i);
}
dfs(1);
for(int i=2;i<=n;i++)printf("%.8lf\n",calc(i,ans[i]));
return 0;
}
rp++
原文：https://www.cnblogs.com/wzc521/p/11395990.html