HDU 2586:How far away ？

题目很简单，可以用很多方法写
本人只是想练习一下两种求LCA的方法

基于RMQ思想的LCA

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=40000+100;

struct Edge{

    int from,to;
    int len;
    int next;
}edge[maxn*2];
int head[maxn],tot;

int first[maxn],dfs_c[maxn*2],dep_c[maxn*2],dfs_cc;

int dis[maxn];
int n,m;

int fa[maxn*2][20];
int kaven[20];

inline void AddEdge(int u,int v,int len){

    edge[tot].from=u;
    edge[tot].to=v;
    edge[tot].len=len;
    edge[tot].next=head[u];
    head[u]=tot++;

    edge[tot].from=v;
    edge[tot].to=u;
    edge[tot].len=len;
    edge[tot].next=head[v];
    head[v]=tot++;
}

inline void dfs(int u,int f,int d,int l){

    first[u]=++dfs_cc;
    dfs_c[dfs_cc]=u;
    dep_c[dfs_cc]=d;
    dis[u]=l;
    for(int i=head[u];i!=-1;i=edge[i].next){

        Edge e=edge[i];
        int v=e.to;
        if(v==f) continue;
        dfs(v,u,d+1,l+e.len); 
        dfs_c[++dfs_cc]=u;
        dep_c[dfs_cc]=d;
    }
}

inline void RMQ(){

    for(int i=1;i<=dfs_cc;i++) fa[i][0]=i;
    for(int i=1;(1<<i)<=dfs_cc;i++){

        for(int j=1;j+(1<<i)-1<=dfs_cc;j++){

            int l=fa[j][i-1];
            int r=fa[j+(1<<(i-1))][i-1];
            if(dep_c[l]<dep_c[r]) fa[j][i]=l;
            else fa[j][i]=r;
        }
    }
}

inline int getLca(int u,int v){

    u=first[u];
    v=first[v];
    if(u>v) swap(u,v);
    int len=v-u;
    int i;
    for(i=0;i<20;i++) if(kaven[i+1]>=len) break;
    int l=fa[u][i];
    int r=fa[u+(1<<i)][i];
    if(dep_c[l]<dep_c[r]) return dfs_c[l];
    return dfs_c[r];
}

inline void init(){

    tot=dfs_cc=0;
    for(int i=1;i<=n;i++) head[i]=-1;
}

inline void scan_d(int &res){

    res=0;
    char ch;
    ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') res=res*10+(ch-'0'),ch=getchar();
}

inline void print_d(int res){

    if(res>9) print_d(res/10);
    putchar(res%10+'0');
}

int main(){

    for(int i=0;i<20;i++) kaven[i]=1<<i;
    int T;
    scan_d(T);
    while(T--){

        scan_d(n);
        scan_d(m);
        init();
        for(int i=1;i<n;i++){

            int u,v,len;
            scan_d(u);
            scan_d(v);
            scan_d(len);
            AddEdge(u,v,len);
        }
        dfs(1,-1,1,0);
        RMQ();
        for(int i=1;i<=m;i++){

            int u,v;
            scan_d(u);
            scan_d(v);
            int lca=getLca(u,v);
            int len=dis[u]+dis[v]-2*dis[lca];
            printf("%d\n",len);
        }
    }
}

tarjan求LCA

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=40000+100;

struct Edge{

    int from,to;
    int len;
    int next;
}edge[maxn*2];
int head[maxn],tot;

struct Query{

    int u,v;
    int lca;
    int next;
}query[maxn*2];
int head_q[maxn],toq;

int dis[maxn];
int n,m;
int fa[maxn];
bool vis[maxn];

inline void AddEdge_q(int u,int v){

    query[toq].u=u;
    query[toq].v=v;
    query[toq].lca=-1;
    query[toq].next=head_q[u];
    head_q[u]=toq++;

    query[toq].u=v;
    query[toq].v=u;
    query[toq].lca=-1;
    query[toq].next=head_q[v];
    head_q[v]=toq++;
}

inline void AddEdge(int u,int v,int len){

    edge[tot].from=u;
    edge[tot].to=v;
    edge[tot].len=len;
    edge[tot].next=head[u];
    head[u]=tot++;

    edge[tot].from=v;
    edge[tot].to=u;
    edge[tot].len=len;
    edge[tot].next=head[v];
    head[v]=tot++;
}

inline int Find(int x){

    if(x!=fa[x]) fa[x]=Find(fa[x]);
    return fa[x];
}

inline void dfs(int u,int l){

    vis[u]=true;
    dis[u]=l;
    for(int i=head[u];i!=-1;i=edge[i].next){

        Edge e=edge[i];
        int v=e.to;
        if(vis[v]) continue;
        dfs(v,l+e.len); 
        fa[v]=u;
    }
    for(int i=head_q[u];i!=-1;i=query[i].next){

        Query q=query[i];
        int v=q.v;
        if(vis[v]){

            query[i].lca=query[i^1].lca=Find(v);
        }
    }
}

inline void init(){

    tot=toq=0;
    for(int i=1;i<=n;i++) head[i]=head_q[i]=-1,fa[i]=i,vis[i]=false;
}

inline void scan_d(int &res){

    res=0;
    char ch;
    ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') res=res*10+(ch-'0'),ch=getchar();
}

inline void print_d(int res){

    if(res>9) print_d(res/10);
    putchar(res%10+'0');
}

int main(){

    int T;
    scan_d(T);
    while(T--){

        scan_d(n);
        scan_d(m);
        init();
        for(int i=1;i<n;i++){

            int u,v,len;
            scan_d(u);
            scan_d(v);
            scan_d(len);
            AddEdge(u,v,len);
        }
        for(int i=1;i<=m;i++){

            int u,v;
            scan_d(u);
            scan_d(v);
            AddEdge_q(u,v);
        }
        dfs(1,0);
        for(int i=1;i<=m;i++){

            int j=2*(i-1);   // 或者 j = 2*i-1 
            int u=query[j].u;
            int v=query[j].v;
            int lca=query[j].lca;
            int len=dis[u]+dis[v]-2*dis[lca];
            printf("%d\n",len);
        }
    }
}