树剖求助

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
//#include <windows.h>
#define MAXN 1000000

using namespace std;

inline int read()
{
    register int x = 0 , f = 1; char c = getchar();
    while( c > '9' || c < '0' ) { if( c == '-' ) f = -1; c = getchar(); }
    while( c >= '0' && c <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( c ^ 48 ); c= getchar(); }
    return f * x;
}

int n , m , s;
int fa[ MAXN ] , son[ MAXN ] , head[ MAXN ] , num , L[ MAXN ] , depth[ MAXN ] , H_son[ MAXN ];

struct node{
    int u , v , next;
}edge[ MAXN ];

void build( register int u , register int  v )
{
    num ++;
    edge[ num ].u = u;
    edge[ num ].v = v;
    edge[ num ].next = head[ u ];
    head[ u ] = num;
}

void dfs_1( register int x , register int F )
{
    H_son[ x ] = 1 , depth[ x ] = depth[ F ] + 1 , fa[ x ] = F;
    for( register int i = head[ x ] ; i ; i = edge[ i ].next )
    {
        register int v = edge[ i ].v;
        if( v != F )
        {
            dfs_1( v , x );
            H_son[ x ] += H_son[ v ];
            if( H_son[ son[ x ] ] < H_son[ v ] || !son[ x ] )
            {
                son[ x ] = v;
            }
        }
    }
}

void dfs_2( register int x , register int l )
{
    L[ x ] = l;
    if( son[ x ] )
    {
        dfs_2( son[ x ] , l );
    }
    else return ;
    for( register int i = head[ x ] ; i ; i = edge[ i ].next )
    {
        register int v = edge[ i ] .v;
        if( v != fa[ x ] && v != son[ x ] )
        {
            dfs_2( v , v );
        }
    }
}

int find( int x , int y )
{
    while( L[ x ] != L[ y ] )
    {
        if( depth[ L[ x ] ] < depth[ L[ y ] ] )
        {
            swap( x , y );
        }
        x = fa[ L[ x ] ];
//		if( depth[ L[ x ] ] >= depth[ L[ y ] ] )
//		{
//			x = fa[ L[ x ] ];
//		}
//        else
//		{
//			y = fa[ L[ y ] ];
//		}
    }
    return depth[ x ] < depth[ y ] ? x : y;
}

int main()
{
    n =read() , m = read() , s = read();
    for( register int i = 1 ; i < n ; i ++ )
    {
        register int u = read() , v = read();
        build( u , v );
        build( v , u );
    }
    dfs_1( s , 0 );
    dfs_2( s , s );
    while( m -- )
    {
        register int a = read() , b = read();
        printf( "%d" , find( a , b ) );
        putchar('\n');
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Max 1000000
using namespace std;
int N,M,S,x,y,cnt,list[Max],s[Max],d[Max],f[Max];
int son[Max],c[Max];
struct xo {
    int to,next;
} a[Max];
inline int read()
{
    int x = 0 , f = 1; char c = getchar();
    while( c > '9' || c < '0' ) { if( c == '-' ) f = -1; c = getchar(); }
    while( c >= '0' && c <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( c ^ 48 ); c= getchar(); }
    return f * x;
}
void add(int q,int w) {
    a[++cnt].to=w;
    a[cnt].next=list[q];
    list[q]=cnt;
}
void dfs1(int n,int F) {
    s[n]=1;d[n]=d[F]+1;f[n]=F;
    int V;
    for(int i=list[n];i;i=a[i].next) {
        V=a[i].to;
        if(V!=F) {
            dfs1(V,n);
            s[n]+=s[V];
            if(!son[x]||s[son[n]]<s[V])
                son[n]=V;
        }
    }
}
void dfs2(int n,int C) {
    c[n]=C;
    if(son[n])
        dfs2(son[n],C);
    else
        return;
    int V;
    for(int i=list[n];i;i=a[i].next) {
        V=a[i].to;
        if(V!=f[n]&&V!=son[n])
            dfs2(V,V);
    }
}
int lca(int x,int y) {
	while( c[ x ] != c[ y ] )
	{
		if(d[c[x]]<d[c[y]])
            swap(x,y);
        x = f[ c[ x ] ];
	}
    return d[x]<d[y]?x:y;
}
int main() {
    N = read(), M = read() , S = read();
    for(int i=1;i<=N-1;i++) {
        x = read() , y = read();
        add(x,y);
        add(y,x);
    }
    dfs1(S,0);
    dfs2(S,S);
    for(int i=1;i<=M;i++) {
        x = read() , y = read();
        printf("%d\n",lca(x,y));
    }
    return 0;
}