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
|
#include <vector>
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
const int N=200005;
int n,m,out[N];
int ha[N],hb[N],tot;
int dfnb[N][2],dfntm;
vector<pii> q[N];
struct {int v,next;}e[N*2];
inline void addEdge(int u,int v,int *h){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
namespace CEG{
const int S=N*2*18;
int rt[N],sz,ch[S][2],maxs[S];
inline int copy(int u){
int 大专栏 最近公共祖先 v=++sz;
ch[v][0]=ch[u][0]; ch[v][1]=ch[u][1];
maxs[v]=maxs[u];
return v;
}
void insert(int u,int &v,int l,int r,int L,int R,int x){
v=copy(u);
if(L<=l&&r<=R){
maxs[v]=max(maxs[v],x);
return;
}
int mid=(l+r)>>1;
if(R<=mid) insert(ch[u][0],ch[v][0],l,mid,L,R,x);
else if(mid<L) insert(ch[u][1],ch[v][1],mid+1,r,L,R,x);
else{
insert(ch[u][0],ch[v][0],l,mid,L,mid,x);
insert(ch[u][1],ch[v][1],mid+1,r,mid+1,R,x);
}
}
int query(int u,int l,int r,int pos,int now){
now=max(now,maxs[u]);
if(l==r) return now;
int mid=(l+r)>>1;
if(pos<=mid) return query(ch[u][0],l,mid,pos,now);
else return query(ch[u][1],mid+1,r,pos,now);
}
}
void dfsB(int u,int fa){
dfnb[u][0]=++dfntm;
for(int i=hb[u],v;i;i=e[i].next)
if((v=e[i].v)!=fa)
dfsB(v,u);
dfnb[u][1]=dfntm;
}
void dfsA(int u,int fa){
CEG::insert(CEG::rt[fa],CEG::rt[u],1,n,dfnb[u][0],dfnb[u][1],u);
for(int i=0,sz=q[u].size();i<sz;i++){
int v=q[u][i].first,qid=q[u][i].second;
out[qid]=CEG::query(CEG::rt[u],1,n,dfnb[v][0],0);
}
for(int i=ha[u],v;i;i=e[i].next)
if((v=e[i].v)!=fa)
dfsA(v,u);
}
int main(){
freopen("input.in","r",stdin);
scanf("%d%d",&n,&m);
for(int v=2;v<=n;v++){
int u;
scanf("%d",&u);
addEdge(u,v,ha);
}
for(int v=2;v<=n;v++){
int u;
scanf("%d",&u);
addEdge(u,v,hb);
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
q[x].pb(mp(y,i));
}
dfsB(1,0);
dfsA(1,0);
for(int i=1;i<=m;i++) printf("%dn",out[i]);
return 0;
}
|