倍增LCA

#include<cstdio>
#include<vector>
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int v,next;
}e[5000005];  //存邊
int n;
int cnt;
int head[200005]; 
int dep[200005]; //點的深度
int f[200005][30]; //倍增數組
void add(int u,int v)
{
    e[cnt] = node{v,head[u]};
    head[u] = cnt++;
}
void dfs(int x,int p,int d)  //記錄深度
{
    f[x][0] = p;
    dep[x] = d;
    for(int i = head[x];i!=-1;i=e[i].next)
    {
        int to = e[i].v;
        if(to!=p)
        {
            dfs(to,x,d+1);
        }
    }
}
void init() //記錄倍增數組
{
    dfs(1,0,0);
    for(int i=1;i<=21;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            f[j][i] = f[f[j][i-1]][i-1];
        }
    }
}
int lca(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);//使x為深的
    int diff = dep[x] - dep[y];
    for(int i=21;i>=0;i--)  //找到x的與y同深度的祖先
    {
        //if(diff >> 1 & 1)
        if(dep[x]>dep[y]&&dep[f[x][i]] >= dep[y]&&f[x][i] != 0)
        {
            x = f[x][i];
        }
    }
    if(x == y) return x;
    for(int i=21;i>=0;i--) //找的最後一個不相等的祖先
    {
        if(f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];//最後一個不相等的上一個祖先即LCA
}

int main()
{
    scanf("%d",&n);
    int i,u,v;
    cnt = 0;
    for(i=1;i<=n;i++)
    {
        head[i] = -1;
    }
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    if(n==1)
    {
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d%d",&u,&v);
            printf("1\n");
        }
        return 0;
    }
    memset(f,0,sizeof(f));
    init();
    lca(1,2);
    return 0;
}