题目大意
题目分析
考虑一下什么样的答案是不可能被选取的。
对于$u$的祖先$v$，当$v$的深度减大的时候，$dis(u,v)$增小，若$c_v$变大肯定不会成为最优值。
实际上我们维护的是这样的一个下凸包：
答案实际上就是给定点在凸包上的切线。
考虑使用CDQ分治解决这个问题。
如何在树上进行CDQ分治？
因为这道题是统计来自每个点祖先的信息，故考虑树的上半部分对下半部分的贡献。
如何对树进行分治呢？
注意序列的分治我们每次把序列分成一半，如果树我们也能将其分成一半就好了。
将树分成一半，可以考虑从重心拆分。
因此算法步骤是这样的：
CDQBinary(x)表示对$x$的子树中尚未被访问的点进行分治。
第一步，求出重心，并将重心的子结点设为访问。
1
2
3
4
5
| Min=0x7fffffff/2;
Get_Size(Now);
Get_Core(Now,Now);
int c=Core;
for(auto& Next:edges[c])vst[Next]=1;
|
第二步，递归根到重心的这部分子树（结点数$O(\frac{n}2)$)。
1
| if(c!=Now)CDQBinary(Now);
|
第三步，处理根到重心的这部分点对重心下方未访问点的贡献。
首先我们先维护上半部分的凸包。
1
2
3
4
5
6
7
8
9
10
11
| top=0;
int p=c,cnt=0;
while(p!=father[Now]) {
tmp[++cnt]=p;
p=father[p];
}
for(int i=cnt; i>=1; i--) {
while(top>1&&Slope(S[top-1],S[top])>=Slope(S[top],tmp[i]))top--;
S[++top]=tmp[i];
}
S[top+1]=0;
|
然后使用凸包更新每个下半部分的结点的答案。
更新时利用二分法找到凸包的切线更新。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void Cal(int Now) {
int Left=1,Right=top;
while(Left<=Right) {
int mid=(Left+Right)>>1;
double k1=Slope(S[mid-1],S[mid]),k2=Slope(S[mid],S[mid+1]),k=Slope(S[mid],Now);
if(k1<=k&&k2>=k) {
f[Now]=min(f[Now],-k);
break;
}
if(k1<=k)Left=mid+1;
else Right=mid-1;
}
for(auto& Next:edges[Now]) {
if(vst[Next])continue;
Cal(Next);
}
}
for(auto& Next:edges[c])Cal(Next);
|
最后递归下半层。
1
2
| for(auto& Next:edges[c])
if(Size[Next]>1)CDQBinary(Next);
|
因为每次CDQ分治的时候结点数减半，但是每次CDQ有一个二分操作，所以时间复杂度是$O(n\log^2n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=500005;
int n,Size[maxn],Maxs[maxn],Depth[maxn],father[maxn],tmp[maxn],vst[maxn],S[maxn],c[maxn],Min=0x7fffffff/2,Core,top=0;
double f[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now,int depth) {
Depth[Now]=depth;
for(auto& Next:edges[Now])Dfs(Next,depth+1);
}
void Get_Size(int Now) {
Size[Now]=1;
Maxs[Now]=0;
for(auto& Next:edges[Now]) {
if(vst[Next])continue;
Get_Size(Next);
Size[Now]+=Size[Next];
Maxs[Now]=max(Maxs[Now],Size[Next]);
}
}
void Get_Core(int num,int Now) {
Maxs[Now]=max(Maxs[Now],Size[num]-Size[Now]);
if(Maxs[Now]<Min) {
Min=Maxs[Now];
Core=Now;
}
for(auto& Next:edges[Now]) {
if(vst[Next])continue;
Get_Core(num,Next);
}
}
double Slope(int x,int y) {
if(!x)return -1e17;
if(!y)return 1e17;
return (double)(c[x]-c[y])/(Depth[x]-Depth[y]);
}
void Cal(int Now) {
int Left=1,Right=top;
while(Left<=Right) {
int mid=(Left+Right)>>1;
double k1=Slope(S[mid-1],S[mid]),k2=Slope(S[mid],S[mid+1]),k=Slope(S[mid],Now);
if(k1<=k&&k2>=k) {
f[Now]=min(f[Now],-k);
break;
}
if(k1<=k)Left=mid+1;
else Right=mid-1;
}
for(auto& Next:edges[Now]) {
if(vst[Next])continue;
Cal(Next);
}
}
void CDQBinary(int Now) {
Min=0x7fffffff/2;
Get_Size(Now);
Get_Core(Now,Now);
int c=Core;
for(auto& Next:edges[c])vst[Next]=1;
if(c!=Now)CDQBinary(Now);
top=0;
int p=c,cnt=0;
while(p!=father[Now]) {
tmp[++cnt]=p;
p=father[p];
}
for(int i=cnt; i>=1; i--) {
while(top>1&&Slope(S[top-1],S[top])>=Slope(S[top],tmp[i]))top--;
S[++top]=tmp[i];
}
S[top+1]=0;
for(auto& Next:edges[c])Cal(Next);
for(auto& Next:edges[c])
if(Size[Next]>1)CDQBinary(Next);
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)c[i]=Get_Int();
for(int i=2; i<=n; i++) {
father[i]=Get_Int();
AddEdge(father[i],i);
f[i]=1e17;
}
Dfs(1,1);
CDQBinary(1);
for(int i=2; i<=n; i++)printf("%0.10lf\n",f[i]);
return 0;
}
|
