题意:给了两棵树，他们的跟都是1，然后询问，u,v 表 示在第一棵树上在u点往根节点走 ， 第二棵树在v点往根节点走，然后求他们能到达的最早的那个共同的点
解:
我们将第一棵树进行书链剖，然后第二棵树采用主席树，他的信息来自他的父亲节点，每个点存他在第一棵树 树链剖分后的位置，这样我们每次查询uv的时候我们只要 我们选取u和top[u]这段区间在主席树v这颗树上找，在这个区间能取到的最大值，一旦存在，这个最大值就我们要的，这个点保存着他到根节点这条路上所有点在第一棵树剖分后的位置
#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <string.h> using namespace std; const int maxn=100005; const int MMAXN=100005*20; int H[maxn],to[maxn*2],nx[maxn*2],numofE; int son[maxn],depth[maxn],fa[maxn],num[maxn],top[maxn]; int p[maxn],fp[maxn],pos,sizoftree; int Ls[MMAXN],Rs[MMAXN],Mav[MMAXN],T[maxn],depth2[maxn]; void init(int n) { sizoftree=pos=numofE=0; for(int i=0; i<=n; i++)H[i]=0; T[0]=Ls[0]=Rs[0]=Mav[0]=sizoftree=0; } void add(int u,int v) { numofE++; to[numofE]=v; nx[numofE]=H[u]; H[u]=numofE; } void dfs(int cur, int per, int dep) { depth[cur]=dep; son[cur]=-1; fa[cur]=per; num[cur]=1; for(int i=H[cur]; i; i=nx[i]) { int tt=to[i]; if(tt==per)continue; dfs(tt,cur,dep+1); num[cur]+=num[tt]; if(son[cur]==-1 || num[ son[cur] ]<num[tt]) son[cur]=tt; } } void finde(int cur, int per, int tp) { top[cur]=tp; pos++; p[cur]=pos; fp[pos]=cur; if(son[cur]!=-1) finde(son[cur],cur,tp); for(int i=H[cur]; i; i=nx[i]) { int tt=to[i]; if(tt==per||tt==son[cur])continue; finde(tt,cur,tt); } } void insert(int L, int R, int K,int pre ,int &x) { x=++sizoftree; Ls[x]=Ls[pre]; Rs[x]=Rs[pre]; Mav[x]=max( Mav[pre],K); if(L==R)return ; int mid=(L+R)>>1; if(K<=mid)insert(L,mid,K,Ls[pre],Ls[x]); else insert(mid+1,R,K,Rs[pre],Rs[x]); } int cL,cR; int query(int L, int R,int root) { if(cL<=L&&R<=cR)return Mav[root]; if(Mav[root]==0)return 0; int mid=(L+R)>>1; int a1=0,a2=0; if(cL<=mid)a1=query(L,mid,Ls[root]); if(cR>mid)a2=query(mid+1,R,Rs[root]); return max(a1,a2); } int solve(int u, int v,int n) { int fu=top[u]; int ret; while(true) { cL=p[fu];cR=p[u]; ret=query(1,n,T[v]); if(ret)break; u=fa[fu]; fu=top[u]; } return fp[ret]; } int main() { int n,m; while(scanf("%d%d",&n,&m)==2) { init(n); for(int i=2; i<=n; i++) { int u; scanf("%d",&u); add(i,u); add(u,i); } dfs(1,1,1); finde(1,1,1); depth2[1]=1; insert(1,n,1,T[0],T[1]); for(int i=2; i<=n; i++) { int u; scanf("%d",&u); depth2[i]=depth2[u]+1; insert(1,n,p[i],T[u],T[i]); } int ans=0; for(int i=0; i<m; i++) { int u,v; scanf("%d%d",&u,&v); u=(u+ans)%n+1; v=(v+ans)%n+1; ans=solve(u,v,n); printf("%d %d %d ",ans,depth[u]-depth[ans]+1,depth2[v]-depth2[ans]+1); } } return 0; }