LCA之树链剖分 zhn_666的lca 模板
#include <cstdio>
#include <algorithm>
#define N 500005
using namespace std;
int n,m,s,tot,dcnt;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int head[N*2],mp[N];
struct EDGE{
    int to,nex;
}ed[N*2];
struct tree{
    int son,fa,top,sz,s,e,dep;
}tr[N];
inline void add(int x,int y){
    ++tot;
    ed[tot].nex=head[x];
    head[x]=tot;
    ed[tot].to=y;
}
void dfs1(int u){
    tr[u].sz=1;
    for(int i=head[u];i;i=ed[i].nex){
        if(ed[i].to!=tr[u].fa){
            tr[ed[i].to].fa=u;
            tr[ed[i].to].dep=tr[u].dep+1;
            dfs1(ed[i].to);
            tr[u].sz+=tr[ed[i].to].sz;
            if(tr[ed[i].to].sz>tr[tr[u].son].sz)
              tr[u].son=ed[i].to;
        }
    }
}
void dfs2(int u,int top){
    tr[u].top=top;
    tr[u].s=++dcnt;
    mp[dcnt]=u;
    if(tr[u].son) {
        dfs2(tr[u].son,top);
        for(int i=head[u];i;i=ed[i].nex)
        if(ed[i].to!=tr[u].fa&&ed[i].to!=tr[u].son)
        dfs2(ed[i].to,ed[i].to);
    }
    tr[u].e=dcnt;
}
int find(int x,int y){
    int f1=tr[x].top;
    int f2=tr[y].top;
    while(f1!=f2){
        if(tr[f1].dep<tr[f2].dep){
            swap(f1,f2);
            swap(x,y);
        }
        x=tr[f1].fa;
        f1=tr[x].top;
    }
    if(tr[x].dep<tr[y].dep) return x;
    else return y;
}
int main(){
    n=read();m=read();
    s=read();
    for(int i=1;i<n;i++){
        int x,y;
        x=read();
        y=read();
        add(x,y);
        add(y,x);
    }
    tr[s].dep=0;
    dfs1(s);
    dfs2(s,s);
    for(int i=1;i<=m;i++){
        int x,y;
        x=read();
        y=read();
        printf("%lld\n",find(x,y));
    }
    return 0;
}

最稳的lca 写法哈哈哈

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议