lca 在线算法 zoj 3195

浏览数：43 / 时间：2015年06月08日

题目大意是对给定3点，求这三个点只之间的最短距离。三个点两两组合求lca:dis[u]+dis[v]-dis[lca];将三个组合值相加除以2即为答案。

RMQ算法学习：http://blog.csdn.net/liang5630/article/details/7917702

对于lca->RMQ的转化，可以参看巨巨写的ppt。

技术分享

欧拉序列：euler[N];

深度序列：depth[N];

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn=50000+10;
const int M=20;
int n,tot,T;
int vis[maxn],euler[maxn<<1],depth[maxn<<1],pos[maxn],bit[M],head[maxn],dis[maxn];
int dp[maxn<<1][M];
struct node
{
    int v,w,next;
}e[maxn<<1];
inline void Swap(int &a,int &b)
{
    int c;
    c=a;
    a=b;
    b=c;
}
void build(int u,int v,int w)
{
    e[T].v=v;
    e[T].w=w;
    e[T].next=head[u];
    head[u]=T++;
}
void init()
{
    memset(vis,0,sizeof(vis));
    memset(head,-1,sizeof(head));
    memset(dis,0,sizeof(dis));
    T=0;
    tot=0;
    int u,v,w;
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        build(u,v,w);
        build(v,u,w);
    }
}
void dfs(int u,int dep)
{
    vis[u]=1;
    euler[++tot]=u;
    pos[u]=tot;
    depth[tot]=dep;
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].v;
        if(!vis[v])
        {
            int v=e[i].v;
            dis[v]=dis[u]+e[i].w;
            dfs(v,dep+1);
            euler[++tot]=u;
            depth[tot]=dep;
        }

    }
}
void ST(int len)
{
    int k=(int)(log(len*1.0)/log(2.0));
    for(int i=1;i<=len;i++)
        dp[i][0]=i;
    for(int j=1;j<=k;j++)
    {
        for(int i=1;i+bit[j]<=len;i++)
        {
            int l=dp[i][j-1];
            int r=dp[i+bit[j-1]][j-1];
            dp[i][j]=depth[l]<depth[r]?l:r;
        }
    }
}
int RMQ(int x,int y)
{
    int k=(int)(log((y-x+1)*1.0)/log(2.0));
    int l=dp[x][k];
    int r=dp[y-bit[k]+1][k];
    return depth[l]<depth[r]?l:r;
}
int LCA(int u,int v)
{
    int l=pos[u];
    int r=pos[v];
    if(l>r)
        Swap(l,r);
    int res=RMQ(l,r);
    return euler[res];
}
int main()
{
    //freopen("in.txt","r",stdin);
    for(int i=0;i<=M;i++)
        bit[i]=1<<i;
    int kase=0;
    while(~scanf("%d",&n))
    {
        if(kase!=0)
            printf("\n");
        kase++;
        init();
        dfs(0,1);
        ST(2*n-1);
        int q;
        scanf("%d",&q);
        int a,b,c,lca[3],p;
        while(q--)
        {
            scanf("%d%d%d",&a,&b,&c);
            p=LCA(a,b);
            lca[0]=dis[a]+dis[b]-2*dis[p];
            p=LCA(b,c);
            lca[1]=dis[b]+dis[c]-2*dis[p];
            p=LCA(a,c);
            lca[2]=dis[a]+dis[c]-2*dis[p];
            printf("%d\n",(lca[0]+lca[1]+lca[2])/2);
        }
    }
    return 0;
}