链接：http://codeforces.com/contest/1062/problem/E
思路：求一个区间内删去一个点后深度最深的lca，首先我们要了解与一个性质，如果按照dfs序下来，那么一个区间内的lca就等于dfs区间中dfs序最小和最大的两个点的lca（其他的点一定都属于这两个点lca的子树里面，可自行证明），这个性质是我们做这个题的前提题，然后区间最值的维护方法有很多，这里我用了线段树不过显得麻烦了，简单一点可以用st表，首先选出最大点u和最小点v，去除最大掉就在（l,u-1）U (u+1,r)中寻找最大值与v求lca，同理对于去除v，最终比较一下两种情况下谁的lca的深度最深就是答案了。顺便用这个题练习了一下倍增法求lca以及lca转RMQ问题，tarjan离线在这个题上我还不太清楚怎么使用，反正通过这个题把三个求lca的板子都顺带写了一下，至于树剖的版本等以后学了再补上来吧。

倍增法版本：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
int n,q,t;
int maxv[maxn<<2],minv[maxn<<2],mini[maxn<<2],maxi[maxn<<2];
int in[maxn];

void pushup(int o){
   if(minv[o<<1]<minv[o<<1|1]){
       minv[o] = minv[o<<1];
       mini[o] = mini[o<<1];
   }
   else{
       minv[o] = minv[o<<1|1];
       mini[o] = mini[o<<1|1];
   }
   if(maxv[o<<1]>maxv[o<<1|1]){
       maxv[o] = maxv[o<<1];
       maxi[o] = maxi[o<<1];
   }
   else{
       maxv[o] = maxv[o<<1|1];
       maxi[o] = maxi[o<<1|1];
   }
}

void build(int o,int l,int r){
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
  }
  else{
    minv[o] = maxv[o] = in[l];
    mini[o] = l;
    maxi[o] = l;
  }
}

int querymin(int o,int tl,int tr,int l,int r){
  if(tr<l||r<tl)return maxn-1;
  if(l<=tl&&tr<=r)return mini[o];
  int mid = (tl+tr)>>1;
  int ret1 = querymin(o<<1,tl,mid,l,r);
  int ret2 = querymin(o<<1|1,mid+1,tr,l,r);
    if(in[ret1]<in[ret2])return ret1;
    return ret2;
}

int querymax(int o,int tl,int tr,int l,int r){
  if(tr<l||r<tl)return maxn-2;
  if(l<=tl&&tr<=r)return maxi[o];
  int mid = (tl+tr)>>1;
    int ret1 = querymax(o<<1,tl,mid,l,r);
    int ret2 = querymax(o<<1|1,mid+1,tr,l,r);
   if(in[ret1]>in[ret2])return ret1;
    return ret2;
}


struct edge{
    int from,to,dist;
};

struct LCA{
    int f[maxn][25];
    int d[maxn];
    int dep[maxn];
    vector<int> G[maxn];
    vector<edge> edges;
    int n,m,t;

    void init(int n,int t){
        this->n = n;
        this->t = t;
        for(int i=0;i<=n;i++)G[i].clear(),dep[i] = d[i] = 0;
        edges.clear();
    }

    void addedge(int from,int to,int dist = 1){
        edges.push_back(edge{from,to,dist});
        m = edges.size();
        G[from].push_back(m-1);
    }

    void bfs(){
        queue<int> q;
        q.push(1);
        dep[1] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i=0;i<G[u].size();i++){
                edge e = edges[G[u][i]];
                int v = e.to;
                if(dep[v])continue;
                dep[v] = dep[u] + 1;    
                d[v] = d[u] + e.dist;
                f[v][0] = u;
                for(int j=1;j<=t;j++){
                    f[v][j] = f[f[v][j-1]][j-1];
                    q.push(v);
                }
            }
        }
    }

    int lca(int x,int y){
        if(dep[x]>dep[y])swap(x,y);
        for(int i=t;i>=0;i--){
            if(dep[f[y][i]]>=dep[x])y = f[y][i];
        }
            if(x==y)return x;
        for(int i=t;i>=0;i--){
            if(f[x][i]!=f[y][i])x = f[x][i],y = f[y][i];
        }
        return f[x][0];
    }
}solver;

void dfs(int u,int f){
    in[u] = t++;
    for(int i=0;i<solver.G[u].size();i++){
        edge e = solver.edges[solver.G[u][i]];
        int v = e.to;
        if(v==f)continue;
        dfs(v,u);
    }
}

int main(){
    scanf("%d%d",&n,&q);
    solver.init(n,log(n)/log(2)+1);
    for(int i=2;i<=n;i++){
        int a;
        scanf("%d",&a);
        solver.addedge(i,a);
        solver.addedge(a,i);
    }
    in[maxn-1] = 1e9;
    in[maxn-2] = 0;
    solver.bfs();
    t = 1;
    dfs(1,-1);
    build(1,1,n);
  //  for(int i=1;i<=n;i++)printf("%d %d\n",i,in[i]);
    for(int i=0;i<q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        int u0 = querymax(1,1,n,l,r);
        int v0 = querymin(1,1,n,l,r);
        //printf("%d %d 111111111\n",u0,v0);
        int uu,vv;
        int u1 = querymax(1,1,n,l,u0-1);
        int u2 = querymax(1,1,n,u0+1,r);
        if(in[u1]>in[u2])uu = u1;
        else uu = u2;
        int v1 = querymin(1,1,n,l,v0-1);
        int v2 = querymin(1,1,n,v0+1,r);
        if(in[v1]<in[v2])vv = v1;
        else vv = v2;
       // printf("%d %d %d %d 3333333333\n",u1,u2,v1,v2);
        //printf("%d %d\n",uu,vv);
        int x1 = solver.lca(u0,vv);
        int x2 = solver.lca(uu,v0);
        int res = 0;
        int resx = 1;
        printf("%d %d\n",x1,x2);
        //printf("%d %d %d %d 222222222222\n",x[0],x[1],x[2],x[3]);
        //printf("%d %d %d %d 222222222222\n",solver.dep[x[0]],solver.dep[x[1]],solver.dep[x[2]],solver.dep[x[3]]);
        int resm;
        if(solver.dep[x1]>solver.dep[x2]){
            resm = v0;
            res = solver.dep[x1];
        }
        else{
            resm = u0;
            res = solver.dep[x2];
        }
        printf("%d %d\n",resm,res-1);
    }
    return 0;
}

RMQ版本

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
int n,q,t;
int maxv[maxn<<2],minv[maxn<<2],mini[maxn<<2],maxi[maxn<<2];
int in[maxn];

void pushup(int o){
   if(minv[o<<1]<minv[o<<1|1]){
       minv[o] = minv[o<<1];
       mini[o] = mini[o<<1];
   }
   else{
       minv[o] = minv[o<<1|1];
       mini[o] = mini[o<<1|1];
   }
   if(maxv[o<<1]>maxv[o<<1|1]){
       maxv[o] = maxv[o<<1];
       maxi[o] = maxi[o<<1];
   }
   else{
       maxv[o] = maxv[o<<1|1];
       maxi[o] = maxi[o<<1|1];
   }
}

void build(int o,int l,int r){
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
  }
  else{
    minv[o] = maxv[o] = in[l];
    mini[o] = l;
    maxi[o] = l;
  }
}

int querymin(int o,int tl,int tr,int l,int r){
  if(tr<l||r<tl)return maxn-1;
  if(l<=tl&&tr<=r)return mini[o];
  int mid = (tl+tr)>>1;
  int ret1 = querymin(o<<1,tl,mid,l,r);
  int ret2 = querymin(o<<1|1,mid+1,tr,l,r);
    if(in[ret1]<in[ret2])return ret1;
    return ret2;
}

int querymax(int o,int tl,int tr,int l,int r){
  if(tr<l||r<tl)return maxn-2;
  if(l<=tl&&tr<=r)return maxi[o];
  int mid = (tl+tr)>>1;
    int ret1 = querymax(o<<1,tl,mid,l,r);
    int ret2 = querymax(o<<1|1,mid+1,tr,l,r);
   if(in[ret1]>in[ret2])return ret1;
    return ret2;
}


struct edge{
    int from,to,dist;
};

struct LCA{
    int n,m;
    vector<int> G[maxn];
    vector<edge> edges;
    int ntime;
    int dep[maxn<<1];
    int d[maxn<<1][25];
    int first[maxn];
    int vis[maxn<<1];

    void init(int n){
        this->n = n;
        for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
        ntime = 1;
        memset(vis,0,sizeof(vis));
        memset(first,0,sizeof(first));
        memset(dep,0,sizeof(dep));
    }

    void addedge(int from,int to,int dist = 1){
        edges.push_back(edge{from,to,dist});
        m = edges.size();
        G[from].push_back(m-1);
    }

    void dfs(int u,int f,int d){
        first[u] = ntime;
        vis[ntime] = u;
        dep[ntime++] = d;
        for(int i=0;i<G[u].size();i++){
            edge e = edges[G[u][i]];
            int v = e.to;
            if(v==f)continue;
            dfs(v,u,d+1);
            vis[ntime] = u;
            dep[ntime++] = d;
        }
    }

    void RMQ_init(int len){
        for(int i=1;i<=len;i++)d[i][0] = i;
            for(int j=1;(1<<j)<=len;j++){
                for(int i=1;i+(1<<j)-1<=len;i++){
                    int a = d[i][j-1];
                    int b = d[i+(1<<(j-1))][j-1];
                    if(dep[a]<=dep[b])d[i][j] = a;
                    else d[i][j] = b;
                }
        }
    }

    int query(int l,int r){
        int k = 0;
        while((1<<(k+1))<=r-l+1)k++;
        int a = d[l][k];
        int b = d[r-(1<<k)+1][k];
        if(dep[a]<=dep[b])return a;
        return b;
    }

    int lca(int u,int v){
        int x = first[u];
        int y = first[v];
        if(x>y)swap(x,y);
        return vis[query(x,y)];
    }

    void solve(){
        dfs(1,-1,0);
        RMQ_init(ntime-1);
    }
}solver;

int dd[maxn];

void dfs(int u,int f){
    in[u] = t++;
    for(int i=0;i<solver.G[u].size();i++){
        edge e = solver.edges[solver.G[u][i]];
        int v = e.to;
        if(v==f)continue;
        dd[v] = dd[u] + 1;
        dfs(v,u);
    }
}


int main(){
    scanf("%d%d",&n,&q);
    solver.init(n);
    for(int i=2;i<=n;i++){
        int a;
        scanf("%d",&a);
        solver.addedge(i,a);
        solver.addedge(a,i);
    }
    solver.solve();
    in[maxn-1] = 1e9;
    in[maxn-2] = 0;
    t = 1;
    dd[1] = 1;
    dfs(1,-1);
    build(1,1,n);
    //for(int i=1;i<=n;i++)printf("%d %d\n",i,dd[i]);
    for(int i=0;i<q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        int u0 = querymax(1,1,n,l,r);
        int v0 = querymin(1,1,n,l,r);
        //printf("%d %d 111111111\n",u0,v0);
        int uu,vv;
        int u1 = querymax(1,1,n,l,u0-1);
        int u2 = querymax(1,1,n,u0+1,r);
        if(in[u1]>in[u2])uu = u1;
        else uu = u2;
        int v1 = querymin(1,1,n,l,v0-1);
        int v2 = querymin(1,1,n,v0+1,r);
        if(in[v1]<in[v2])vv = v1;
        else vv = v2;
        //printf("%d %d %d %d 3333333333\n",u1,u2,v1,v2);
        //printf("%d %d\n",uu,vv);
        int x1 = solver.lca(u0,vv);
        int x2 = solver.lca(uu,v0);
        int res = 0;
        int resx = 1;
        //printf("%d %d\n",x1,x2);
        //printf("%d %d %d %d 222222222222\n",x[0],x[1],x[2],x[3]);
        //printf("%d %d %d %d 222222222222\n",solver.dep[x[0]],solver.dep[x[1]],solver.dep[x[2]],solver.dep[x[3]]);
        int resm;
        if(dd[x1]>dd[x2]){  
            resm = v0;
            res = dd[x1];
        }
        else{
            resm = u0;
            res = dd[x2];
        }
        printf("%d %d\n",resm,res-1);
    }
    return 0;
}