LCA（在线ST+tarjan）模板

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <map>

using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define PI acos(-1)
#define DEBUG(a) cout << (a) << endl
typedef long long ll;
int dir8[8][2] = {{1, 2}, {2, 1}, {-1, 2}, {2, -1}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}};
int dir4[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const int INF = 0x3f3f3f3fLL;
const long long LLF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXn = 4e4 + 15;
const int mod = 1e9 + 7;
//priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

struct node
{
    int u, v, w, next;
} edge[2  * MAXn];
int head[MAXn];
bool vis[MAXn];
int dis[MAXn];
int deep[2 * MAXn]; //深度
int first[MAXn];    //首次出现位置
int ver[2 * MAXn];  //遍历顺序
int dp[MAXn * 2][25]; //dp[i][k]=a; 从 i 开始往后 1<<k 个数中最小深度的下标为 a
int n, m, cnt = 1, k;

void add(int u, int v, int w)//链式前向星
{
    edge[cnt] = {u, v, w, head[u]};
    head[u] = cnt++;
}

void init() //初始化
{
    mem(dis, 0);
    mem(vis, 0);
    mem(head, 0);
    cnt = 1;
}

void DFS(int u, int dep)//深搜遍历
{
    vis[u] = 1; //标记为 1 表示已经遍历过次点
    deep[cnt] = dep; //深度为dep
    ver[cnt] = u;  // 遍历次序
    first[u] = cnt++; //u 第一次出现的下坐标为 cnt
    for (int i = head[u]; i != 0; i = edge[i].next) //遍历
    {
        if (!vis[edge[i].v]) //如果没有遍历过，就遍历
        {
            dis[edge[i].v] = dis[u] + edge[i].w; //更新到根节点的距离
            DFS(edge[i].v, dep + 1); 
            ver[cnt] = u; //回溯（又回到了 u 点
            deep[cnt++] = dep;
        }
    }
}

void ST()//更新区间最小值
{
    for (int i = 1; i <= cnt; i++)
        dp[i][0] = i;
    for (int j = 1; j<20; j++)
        for (int i = 1; i + (1 << j) - 1 <= cnt; i++)
        {
            int a = dp[i][j - 1], b = dp[i + (1 << (j - 1))][j - 1];
            dp[i][j] = deep[a] < deep[b] ? a : b; //存下坐标
        }
}

int RMQ(int l, int r) //找 l 和 r 的最近公共祖先的下坐标
{
    int k = 0;
    while (1 << (k + 1) <= r - l + 1) 
        k++;
    int a = dp[l][k];
    int b = dp[r - (1 << k) + 1][k];
    return deep[a] < deep[b] ? a : b;
}

int LCA(int u, int v)
{
    int x = first[u], y = first[v]; //第一次出现的位置
    if (x > y)
        swap(x, y);
    int res = RMQ(x, y); 
    return ver[res]; //返回 u 和 v 的最近公共祖先
}

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <map>

using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define PI acos(-1)
#define DEBUG(a) cout << (a) << endl
typedef long long ll;
int dir8[8][2] = {{1, 2}, {2, 1}, {-1, 2}, {2, -1}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}};
int dir4[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const int INF = 0x3f3f3f3fLL;
const long long LLF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXn = 4e4 + 15;
const int mod = 1e9 + 7;
//priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

struct node
{
    int u, v, w, next;
} edge[2 * MAXn];//边
struct Quiz
{
    int u, v, i, next; //求 u 和 v 的LCA，这是第 i 组提问
} quiz[2*205]; //提问
int head_edge[MAXn];//边
int head_quiz[MAXn]; //提问
bool vis[MAXn]; //是否遍历过
int dis[MAXn]; //到根节点的距离
int fa[MAXn]; //父节点
int lca[205];  //提问的结果，lca[i]=n 表示第 i 组提问的LCA是 n 
int A[205],B[205]; //存提问数据
int n, m, tot1 = 0, tot2 = 0; 

void add_edge(int u, int v, int w){ //链式前向星
    edge[++tot1] = {u, v, w, head_edge[u]};
    head_edge[u] = tot1;
}
void add_quiz(int u,int v,int i){
    quiz[++tot2]={u,v,i,head_quiz[u]};
    head_quiz[u]=tot2;
}
void init(){ //初始化
    mem(dis, 0);
    mem(vis, 0);
    mem(head_edge, 0);
    mem(head_quiz,0);
    tot1 = tot2 = 0;
}
int find(int x) //寻找祖先 + 路径压缩
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Tarjan(int x){ 
    vis[x]=1; //标记
    fa[x]=x;  //父节点更新为自己
    for(int i=head_quiz[x];i!=0;i=quiz[i].next){ //如果有 x，quiz[i].v 这组提问并且 quiz[i].v 被遍历过
        if(vis[quiz[i].v])
            lca[quiz[i].i]=find(quiz[i].v); //quiz[i].v 的祖先即提问的LCA
    }
    for(int i=head_edge[x];i!=0;i=edge[i].next){ //遍历树
        if(!vis[edge[i].v]){
            dis[edge[i].v]=dis[x]+edge[i].w;
            Tarjan(edge[i].v);
            fa[edge[i].v]=x;
        }
    }
}