POJ __1986 Distance Queries （lca+求距离的骚操作）

Description

Input

Output

Sample Input

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6

Sample Output

13
3
36

Hint

Source

USACO 2004 February

               有n个点m个边~a距离b为c（距离root为线性）~后面那个字符没用~询问x个~求dis[i]+dis[j]-2*dis[lca(i,j)];

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=230100;
const int DEG=20;
struct ***
{
    int to,ne,len;
}ed[maxn*2];
int head[maxn],cnt;
int dis[maxn];//计算距离；
void add(int u,int v,int w)
{
    ed[cnt].to=v;
    ed[cnt].len=w;
    ed[cnt].ne=head[u];
    head[u]=cnt++;
}
void init()
{
    cnt=1;
    memset(head,-1,sizeof(head));
    memset(dis,0,sizeof(dis));
}
int fa[maxn][DEG];
int deg[maxn];//深度数组
void BFS(int root)
{
    queue<int>q;
    deg[root]=0;
    fa[root][0]=root;
    q.push(root);
    dis[root]=0;//
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int s=1;s<DEG;s++)
        {
            fa[t][s]=fa[fa[t][s-1]][s-1];
        }
        for(int s=head[t];s!=-1;s=ed[s].ne)
        {
            int v=ed[s].to;
            if(v==fa[t][0])
            {
                continue;
            }
            deg[v]=deg[t]+1;
            dis[v]=dis[t]+ed[s].len;//
            fa[v][0]=t;
            q.push(v);
        }
    }
}
int LCA(int u,int v)
{
    if(deg[u]>deg[v])
    {
        swap(u,v);
    }
    int hu=deg[u],hv=deg[v];
    int tu=u,tv=v;
    for(int det=hv-hu,s=0;det;det>>=1,s++)
    {
        if(det&1)
        {
            tv=fa[tv][s];
        }
    }
    if(tu==tv)
    {
        return tu;
    }
    for(int s=DEG-1;s>=0;s--)
    {
        if(fa[tu][s]==fa[tv][s])
        {
            continue;
        }
        tu=fa[tu][s];
        tv=fa[tv][s];
    }
    return fa[tu][0];
}
bool in[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    init();
    memset(in,0,sizeof(in));
    for(int s=1;s<=m;s++)
    {
        int a,b,c;
        char w;
        scanf("%d%d%d %c",&a,&b,&c,&w);
        add(a,b,c);
        add(b,a,c);
        in[b]=1;
    }
    int root;
    for(int s=1;s<=n;s++)
    {
        if(!in[s])
        {
            root=s;
            break;
        }
    }
    BFS(root);
    int te;
    cin>>te;
    while(te--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
      //  cout<<LCA(u,v)<<endl;
        cout<<dis[u]+dis[v]-2*dis[LCA(u,v)]<<endl;
    }
    return 0;
}