首先将权值离散化。
不难想到设 \(f_{u,i}\) 表示以 \(u\) 为根的子树内，最小值为 \(i\) 的最大集合大小（不一定要选 \(u\)）。
特别地，若集合为空，\(i = n + 1\)。
那么对于 \(u\) 和其儿子 \(v\)，容易合并状态 \[ f'_{u,i} = \max\left[\max\limits_{j=i}^{n+1} (f_{u,i} + f_{v,j}),\max\limits_{j=i}^{n+1} (f_{u,j} + f_{v,i})\right] \] 线段树合并维护即可。
代码： 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
using namespace std;
const int N = 2e5;
int n;
int a[N + 5],ind[N + 5],len;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
namespace SEG
{
struct node
{
int val,tag;
int ls,rs;
} seg[(N << 5) + 5];
inline void push(int p)
{
if(seg[p].tag)
{
if(seg[p].ls)
seg[seg[p].ls].val += seg[p].tag,
seg[seg[p].ls].tag += seg[p].tag;
if(seg[p].rs)
seg[seg[p].rs].val += seg[p].tag,
seg[seg[p].rs].tag += seg[p].tag;
seg[p].tag = 0;
}
}
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
!p && (seg[p = ++tot] = seg[0],1),seg[p].val = max(seg[p].val,k);
if(tl == tr)
return ;
push(p);
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int p,int tl,int tr)
{
if(!p || l <= tl)
return seg[p].val;
push(p);
int mid = tl + tr >> 1;
int ret = -0x3f3f3f3f;
l <= mid && (ret = max(ret,query(l,seg[p].ls,tl,mid)));
ret = max(ret,query(l,seg[p].rs,mid + 1,tr));
return ret;
}
int merge(int p,int q,int ptag,int qtag,int tl,int tr)
{
if(!p && !q)
return 0;
if(!p)
{
seg[q].val += qtag,seg[q].tag += qtag;
return q;
}
if(!q)
{
seg[p].val += ptag,seg[p].tag += ptag;
return p;
}
if(tl == tr)
{
ptag = max(ptag,seg[q].val),qtag = max(qtag,seg[p].val);
seg[p].val = max(seg[p].val + ptag,seg[q].val + qtag);
return p;
}
push(p),push(q);
int mid = tl + tr >> 1;
int prval = seg[seg[p].rs].val;
int qrval = seg[seg[q].rs].val;
seg[p].ls = merge(seg[p].ls,seg[q].ls,max(ptag,qrval),max(qtag,prval),tl,mid);
seg[p].rs = merge(seg[p].rs,seg[q].rs,ptag,qtag,mid + 1,tr);
seg[p].val = max(seg[seg[p].ls].val,seg[seg[p].rs].val);
return p;
}
}
int fa[N + 5];
int rt[N + 5];
void dfs(int p)
{
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
fa[to[i]] = p,
dfs(to[i]),
rt[p] = SEG::merge(rt[p],rt[to[i]],0,0,1,len);
SEG::insert(a[p],1 + max(SEG::query(a[p],rt[p],1,len),0),rt[p],1,len);
}
int main()
{
SEG::seg[0].val = -0x3f3f3f3f;
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),ind[i] = a[i];
sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
for(register int i = 1;i <= n;++i)
a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
int u;
for(register int i = 2;i <= n;++i)
scanf("%d",&u),add(u,i);
dfs(1);
printf("%d\n",SEG::seg[rt[1]].val);
}