给两颗标号从1...n的树，保证标号小的点一定在上面。每次询问A树上的x点，和B树上的y点同时向上走，最近的相遇点和x,y到这个点的距离。
比赛的时候想用倍增LCA做，但写渣了。。。。后来看到题解是主席树就写了一发
呆马：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <vector> 7 #define inf 1000000007 8 #define maxn 100020 9 #define maxm 4200 10 11 using namespace std; 12 13 int fa[maxn],ga[maxn],ll[maxn],rr[maxn],dep[maxn],gap[maxn]; 14 int n,m,cnt; 15 16 struct node 17 { 18 node *lc, *rc; 19 int key, cov; 20 node(){ 21 key=0; 22 cov=0; 23 lc=rc=NULL; 24 } 25 }; 26 27 struct ChairManTree 28 { 29 node *tree,*rot[maxn]; 30 int tot; 31 node *new_node(){ return &tree[++tot];} 32 node *build(int l, int r) 33 { 34 node *now=new_node(); 35 now->cov=now->key=0; 36 if (l==r) return now; 37 int mid=(l+r)>>1; 38 now->lc=build(l,mid); 39 now->rc=build(mid+1,r); 40 return now; 41 } 42 43 void down(node *p) 44 { 45 if (p->cov) 46 { 47 node *nl=new_node(); 48 node *nr=new_node(); 49 *nl=*p->lc; 50 *nr=*p->rc; 51 nl->key=max(p->lc->key,p->cov); 52 nl->cov=max(p->lc->cov,p->cov); 53 nr->key=max(p->rc->key,p->cov); 54 nr->cov=max(p->rc->cov,p->cov); 55 p->lc=nl; 56 p->rc=nr; 57 p->cov=0; 58 } 59 } 60 61 node *change(node *p, int l, int r, int ll, int rr, int x) 62 { 63 node *now=new_node(); 64 if (ll<=l && r<=rr) 65 { 66 *now=*p; 67 now->key=max(now->key,x); 68 now->cov=max(now->cov,x); 69 return now; 70 } 71 down(p); 72 *now=*p; 73 int mid=(l+r)>>1; 74 if (ll<=mid) now->lc=change(p->lc, l, mid, ll, rr, x); 75 if (rr>mid) now->rc=change(p->rc, mid+1, r, ll, rr, x); 76 return now; 77 } 78 79 int query(node *now, int l, int r, int x) 80 { 81 if (l==r) return now->key; 82 down(now); 83 int mid=(l+r)>>1; 84 if (x<=mid) return query(now->lc, l, mid, x); 85 else return query(now->rc, mid+1, r, x); 86 } 87 88 void write(node *now,int l,int r) 89 { 90 if (l==r) 91 { 92 cout<<now->key; 93 return ; 94 } 95 down(now); 96 int mid=(l+r)>>1; 97 write(now->lc,l,mid); 98 write(now->rc,mid+1,r); 99 } 100 101 void init(int n) 102 { 103 tree=new node[n*80]; 104 tot=0; 105 } 106 void clear() 107 { 108 delete [] tree; 109 } 110 }s; 111 112 vector<int> e[maxn]; 113 114 void dfs(int x) 115 { 116 ll[x]=++cnt; 117 int n=e[x].size(); 118 for (int i=0;i<n;i++) 119 { 120 int k=e[x][i]; 121 dfs(k); 122 } 123 rr[x]=cnt; 124 } 125 126 int main() 127 { 128 //freopen("F.in","r",stdin); 129 while (scanf("%d%d",&n,&m)!=EOF) 130 { 131 s.init(n); 132 fa[1]=ga[1]=0; 133 dep[1]=gap[1]=1; 134 for (int i=1;i<=n;i++) e[i].clear(); 135 for (int i=2;i<=n;i++) scanf("%d",&fa[i]), e[fa[i]].push_back(i), dep[i]=dep[fa[i]]+1; 136 for (int i=2;i<=n;i++) scanf("%d",&ga[i]), gap[i]=gap[ga[i]]+1; 137 cnt=0; 138 dfs(1); 139 140 s.rot[0]=s.build(1,n); 141 142 for (int i=1;i<=n;i++) 143 s.rot[i]=s.change(s.rot[ga[i]],1,n,ll[i],rr[i],i); 144 int x,y,ans=0; 145 for (int i=1;i<=m;i++) 146 { 147 scanf("%d%d",&x,&y); 148 x=(x+ans)%n+1, y=(y+ans)%n+1; 149 ans=s.query(s.rot[y],1,n,ll[x]); 150 printf("%d %d %d ",ans,dep[x]-dep[ans]+1, gap[y]-gap[ans]+1); 151 } 152 s.clear(); 153 } 154 return 0; 155 }