重工电子论坛

标题: 【LCA模版】 [打印本页]

作者: love    时间: 2018-6-13 23:26
标题: 【LCA模版】
本帖最后由 李维强-15级 于 2018-6-15 01:40 编辑

[C++] syntaxhighlighter_viewsource syntaxhighlighter_copycode

#include<cstdio>
#include<cmath>
using namespace std;
int n,m,cnt;
int End[5005],Last[5005],Next[5005],Len[5005],F[5005][20],D[5005],Sum[5005][20];
void add(int x,int y,int z){
        End[++cnt]=y;
        Next[cnt]=Last[x];
        Last[x]=cnt;
        Len[cnt]=z;
}
void DFS(int x){
        D[x]=D[F[x][0]]+1;
        for(int i=1;i<=ceil(log2(D[x]));i++)F[x]=F[F[x][i-1]][i-1],Sum[x]=Sum[x][i-1]+Sum[F[x][i-1]][i-1];
        for(int i=Last[x];i;i=Next){
                if(End==F[x][0])continue;
                F[End][0]=x;Sum[End][0]=Len;
                DFS(End);
        }
}
int LCA(int x,int y){
        if(D[x]<D[y])swap(x,y);
        int k=D[x]-D[y],tot=0;
        for(int i=0;i<=ceil(log2(k));i++)if((1<<i)&k)tot+=Sum[x],x=F[x];
        if(x==y)return tot;
        k=D[x];
        for(int i=ceil(log2(k));i>=0;i--)if(F[x]!=F[y])tot+=(Sum[x]+Sum[y]),x=F[x],y=F[y];
        return tot+Sum[x][0]+Sum[y][0];
}
int main(){
        int a,b,c;
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++){
                scanf("%d%d%d",&a,&b,&c);
                add(a,b,c);add(b,a,c);
        }
        DFS(1);
        for(int i=1;i<=m;i++){
                scanf("%d%d",&a,&b);
                printf("%d\n",LCA(a,b));
        }
}





欢迎光临 重工电子论坛 (http://cqutlab.cn/) Powered by Discuz! X3.1