这题说的是给了两棵树，各有100000 个节点，然后Q个操作Q<=50000; 每个操作L1 R1 L2 R2。因为对于每棵树都有一个与本棵树其他点与众不同的值， 最后问 在树上从L1到R1这条路径上与第二棵树L2 到 R2 这条路上的点 的权值相等的有多少个
这题挺麻烦的 写的想吐了
首先将第一棵树进行树剖，然后通过树剖可以离散出这颗树的每个点的编号从1,2,3,4...N1,然后将第二棵树进行树剖，按照树剖的值依次插入，以第一棵树离散出的值为叶节点的函数式线段树，
如果第二棵树的值在第一棵树种中不到，那么就直接将他插在值为0的叶节点上。我们可以知道在书剖中他们在同一条链上是相等的，所以他们在函数式线段树中也是连续的。通过这样我们可以使用类似区间第K大的解法解决这个问题
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#pragma comment(linker,"/STACk:10240000,10240000")
using namespace std;
const int maxn =;
vector<int> F[][maxn],rea[],fro[];
int p[][maxn],fp[][maxn],XX[],top[][maxn];
int depth[][maxn],num[][maxn],son[][maxn],fa[][maxn];
int L1[maxn],V[maxn],data[][maxn],T[maxn];
int Ls[maxn*],Rs[maxn*],Ve[maxn*],len;
struct point{
int x,loc;
bool operator<(const point &A)const{
return x<A.x||(x==A.x&&loc<A.loc);
}
}PP[maxn];
void inti(int loc, int n){
for(int i=; i<=n; ++i)
F[loc][i].clear();
}
void dfs(int loc, int now, int per,int dep){
fa[loc][now]=per;
son[loc][now]=-;
depth[loc][now]=dep;
num[loc][now]=;
int ge=F[loc][now].size();
for(int i=; i<ge; ++i){
int to = F[loc][now][i];
if(to==per||to==now)continue;
dfs(loc,to,now,dep+);
num[loc][now]+=num[loc][to];
if(son[loc][now]==-||num[loc][ son[loc][now] ]<num[loc][to]) son[loc][now]=to;
}
}
void fine(int loc, int now , int X,int per){
top[loc][now]=X;
XX[loc]++;
p[ loc ][ now ]=XX[ loc ];
fp[ loc ][ XX[loc] ]=now;
if( son[ loc ][ now ] != - )
fine( loc , son[loc][now] , X ,now);
int ge=F[loc][now].size();
for(int i=; i<ge; ++i){
int to=F[loc][now][i];
if( to==son[loc][now]||to==now||to==per ) continue;
fine(loc,to,to,now);
}
}
void inser(int L, int R, int K, int per, int &x){
x = ++len;
Ls[x]=Ls[per];
Rs[x]=Rs[per];
Ve[x]=Ve[per]+;
if(L==R)return ;
int mid=(L+R)>>;
if(K<=mid) inser( L, mid , K, Ls[per] , Ls[x] );
else inser( mid+ , R , K , Rs[per] , Rs[x] );
}
int ansed,Lc,Rc;
void query(int L, int R, int per, int cur){
if(Lc<=L&&R<=Rc){
ansed += Ve[cur]-Ve[per];return;
}
if(L>=R)return ;
int mid = (L+R)>>;
if(Lc<=mid) query(L, mid , Ls[per],Ls[cur]);
if(Rc>mid) query(mid+, R, Rs[per],Rs[cur]);
} void solve(int loc, int p1, int p2){
int f1=top[loc][p1],f2=top[loc][p2];
int num=;
while(f1!=f2){
num++;
if(num>) break;
if(depth[loc][f1]<depth[loc][f2]){
int t=p1; p1=p2; p2=t;
t=f1; f1=f2; f2=t;
}
fro[loc].push_back( p[loc][f1] );
rea[loc].push_back( p[loc][p1] );
p1=fa[loc][f1];
f1=top[loc][p1];
}
if(depth[loc][p1]<depth[loc][p2]){
int t=p1; p1=p2; p2=t;
}
fro[loc].push_back(p[loc][p2]);
rea[loc].push_back(p[loc][p1]);
}
int main()
{
int N1, N2;
while(scanf("%d",&N1)==){
for(int i=; i<N1; ++i){
int f;
scanf("%d",&f);
F[][f].push_back(i+);
}
XX[]=;
dfs(,,,);
fine(,,,);
for(int i=; i<N1; ++i){
scanf("%d",&data[][i]);
PP[i].x = data[][i];
PP[i].loc = i+;
}
sort(PP,PP+N1);
for(int i=; i<N1; ++i)
{
V[i]=PP[i].x;
L1[i]=p[ ][ PP[i].loc ];
} scanf("%d",&N2);
for(int i=; i<N2; ++i){
int fa;
scanf("%d",&fa);
F[][fa].push_back(i+);
}
XX[]=;
dfs(,,,);
fine(,,,);
for(int i=; i<=N2; ++i){
scanf("%d",&data[][i]);
int loc = lower_bound(V,V+N1,data[][i])-V;
if(V[loc]==data[][i]){
data[][i]=L1[loc];
}else data[][i]=;
}
Ls[]=Rs[]=Ve[]=len=;
for(int i=; i <= N2; ++ i ){
int loc=fp[ ][ i ];
inser(,N1,data[ ][ loc ],T[ i- ],T[ i ]);
}
int Q;
scanf("%d",&Q);
for(int i=; i<Q; ++i){
int L1,R1,L2,R2;
scanf("%d%d%d%d",&L1,&R1,&L2,&R2);
rea[].clear(); fro[].clear(); rea[].clear(); fro[].clear();
solve(,L1,R1);
solve(,L2,R2);
ansed=;
for(int j=; j<(int)rea[].size(); ++j){
Lc=fro[][j]; Rc=rea[][j];
if(Lc>Rc){ int t=Lc; Lc=Rc; Rc=t; }
for(int k=; k<(int)rea[].size(); ++k){
int L=fro[][k],R=rea[][k];
if(L>R){ int t=L; L=R; R=t; }
query( ,N1,T[L-],T[R] );
}
}
printf("%d\n",ansed);
}
inti(,N1);
inti(,N2);
}
return ;
}