题目
做法
聪明性是具有传递性的，且排列是固定的
那么先预处理出每个点的名次，用主席树维护\(k\)大值
一眼平衡树，遍历的同时插入\(O(log^2n)\)，总时间复杂度\(O(nlog^2n)\)
显然还需要优化，考虑两个点的比较：按深度递减比较值，如果在等长前提下值相等，则比较深度最浅且的不一样的祖先的大小
这和后缀比较大小相似，我们后缀数组来实现排列的这个过程
Code
#include<bits/stdc++.h>
typedef int LL;
const LL maxn=1e6+9;
inline LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3)+(x<<1)+c-'0'; c=getchar();
}return x*f;
}
struct node{
LL to,nxt;
}dis[maxn];
LL n,num,q,m,tim;
LL head[maxn],fa[maxn],a[maxn],sa[maxn],x[maxn],y[maxn],z[maxn],c[maxn],rk[maxn],inc[maxn][25],b[maxn],dfn[maxn],low[maxn];
inline void Add(LL u,LL v){
dis[++num]=(node){v,head[u]}; head[u]=num;
}
inline void Sort(){
for(LL i=1;i<=n;++i) ++c[x[i]=a[i]];
for(LL i=2;i<=m;++i) c[i]+=c[i-1];
for(LL i=n;i>=1;--i) sa[c[x[i]]--]=i;
for(LL i=1;i<=n;++i) rk[sa[i]]=i;
for(LL len=1,t=0;len<n;len<<=1,++t){
LL num(0);
for(LL i=1;i<=n;++i) z[i]=rk[inc[i][t]];
for(LL i=0;i<=n;++i) c[i]=0;
for(LL i=1;i<=n;++i) ++c[z[i]]; for(LL i=1;i<=n;++i) c[i]+=c[i-1];
for(LL i=n;i>=1;--i) y[c[z[sa[i]]]--]=sa[i];
for(LL i=0;i<=m;++i) c[i]=0;
for(LL i=1;i<=n;++i) ++c[x[i]]; for(LL i=1;i<=m;++i) c[i]+=c[i-1];
for(LL i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i];
for(LL i=1;i<=n;++i) rk[sa[i]]=i;
std::swap(x,y);
x[sa[1]]=num=1;
for(LL i=2;i<=n;++i)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[inc[sa[i]][t]]==y[inc[sa[i-1]][t]])?num:++num;
if(num==n) break;
m=num;
}
}
struct Tree{
LL root[maxn],nod,size[maxn*10],son[maxn*10][2];
void Update(LL &now,LL pre,LL l,LL r,LL x){
now=++nod; size[now]=size[pre]+1;
if(l==r) return; LL mid(l+r>>1);
if(x<=mid){ Update(son[now][0],son[pre][0],l,mid,x); son[now][1]=son[pre][1]; }
else{ Update(son[now][1],son[pre][1],mid+1,r,x); son[now][0]=son[pre][0]; }
}
LL Query1(LL now,LL l,LL r,LL k){
if(l==r) return sa[l]; LL mid(l+r>>1);
LL ret(size[son[now][0]]);
return k<=ret?Query1(son[now][0],l,mid,k):Query1(son[now][1],mid+1,r,k-ret);
}
LL Query2(LL pre,LL now,LL l,LL r,LL k){
if(l==r) return sa[l]; LL mid(l+r>>1);
LL ret(size[son[now][0]]-size[son[pre][0]]);
return k<=ret?Query2(son[pre][0],son[now][0],l,mid,k):Query2(son[pre][1],son[now][1],mid+1,r,k-ret);
}
}T1,T2;
void Fir(LL u){
inc[u][0]=fa[u];
for(LL i=1;i<=20;++i){
inc[u][i]=inc[inc[u][i-1]][i-1]; if(!inc[u][i]) break;
}
for(LL i=head[u];i;i=dis[i].nxt) Fir(dis[i].to);
}
void Dfs(LL u){
dfn[u]=++tim;
T1.Update(T1.root[u],T1.root[fa[u]],1,n,rk[u]);
T2.Update(T2.root[tim],T2.root[tim-1],1,n,rk[u]);
for(LL i=head[u];i;i=dis[i].nxt) Dfs(dis[i].to);
low[u]=tim;
}
inline void Init(){
n=Read(); q=Read();
for(LL i=2;i<=n;++i) Add(fa[i]=Read(),i);
for(LL i=1;i<=n;++i) b[i]=a[i]=Read();
std::sort(b+1,b+1+n); m=std::unique(b+1,b+1+n)-b-1;
for(LL i=1;i<=n;++i) a[i]=std::lower_bound(b+1,b+1+m,a[i])-b;
}
int main(){
Init();
Fir(1);
Sort();
std::reverse(sa+1,sa+1+n);
for(LL i=1;i<=n;++i) rk[sa[i]]=i;
Dfs(1);
while(q--){
LL op(Read()),x(Read());
if(op==1) printf("%d\n",rk[x]);
else{
LL k(Read());
if(op==2) printf("%d\n",T1.Query1(T1.root[x],1,n,k));
else printf("%d\n",T2.Query2(T2.root[dfn[x]-1],T2.root[low[x]],1,n,k));
}
}
return 0;
}