最大后缀值个数 本题看看数据范围其实就大概知道怎么做，然后发现是单调的，直接单调栈就行了
本题有个很坑的细节（其实是我打得太烂了，调了很久没跳出来，一直80分）
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e6+5;
int n
;
int val
[N
],f
[N
],head
[N
],tnt
=0;
struct edge
{
int link
,v
;
}q
[N
<<1];
void put(int x
,int y
){
q
[++tnt
].v
=y
;
q
[tnt
].link
=head
[x
];
head
[x
]=tnt
;
}
int ans
[N
],mly
[N
],cnt
;
int find(int l
,int r
,int vall
){
while(l
<r
){
int mid
=(l
+r
)>>1;
if(mly
[mid
]>=vall
){
l
=mid
+1;
}
else r
=mid
;
}
return l
;
}
void dfs(int s
,int fa
){
for(int i
=head
[s
];i
;i
=q
[i
].link
){
int v
=q
[i
].v
;
if(v
==fa
) continue;
int tp
=cnt
,tp2
=-1,id
=-1;
if(val
[v
]>mly
[cnt
]){
id
=find(1,cnt
,val
[v
]);
tp2
=mly
[id
];
mly
[id
]=val
[v
];
cnt
=id
;
}
else {
id
=cnt
+1,tp2
=mly
[cnt
+1];
mly
[++cnt
]=val
[v
];
}
dfs(v
,s
);
if(tp2
!=-1&&id
!=-1){mly
[id
]=tp2
;}
cnt
=tp
;
}
ans
[s
]=cnt
;
}
int main(){
scanf("%d",&n
);
for(int i
=2;i
<=n
;i
++){
scanf("%d",&f
[i
]);
put(f
[i
],i
);
}
for(int i
=1;i
<=n
;i
++){
scanf("%d",&val
[i
]);
}
mly
[1]=val
[1],cnt
=1;
dfs(1,0);
for(int i
=1;i
<=n
;i
++){
printf("%d ",ans
[i
]);
}
}
```AC代码
id
=cnt
+1,tp2
=mly
[cnt
+1];这段很重要，直接思路是因为原来的串没有这个值（因为原串长小于现在串长），所以不用记录，但实际情况是由于前面有记录，所以如果不修改也会爆
数据
41
1 1 2 1 1 5 2 5 1 10 1 10 3 1 7 5 15 2 11 13 10 5 16 17 19 13 11 14 20 1 9 27 16 3 23 7 19 15 38 7
11 9 1 9 5 12 13 9 11 1 1 6 12 1 16 1 1 17 5 11 11 8 17 5 5 8 1 11 15 5 17 1 17 1 16 3 1 3 13 11 3
以本图为例，到10节点为[11,1],到13为[12],到12为[12,11] 回溯回来就变成11,11 (因为只记录了长度改变，没记录值改变)
