[LCA模版] Distance Queries

题目描述

约翰的奶牛们拒绝跑他的马拉松，因为她们悠闲的生活不能承受他选择的长长的赛道。因此他决心找一条更合理的赛道。此题的输入于第一题相同，紧接着下一行输入一个整数K,以后K行为K个"距离问题"。每个距离问题包括两个整数，就是约翰感兴趣的两个农场的编号，请你尽快算出这两地之间的距离。

N个点，N-1条边

输入

第1行：两个分开的整数：N和M； 

第2..M+1行：每行包括4个分开的内容，F1，F2，L，D分别描述两个农场的编号，道路的长度，F1到F2的方向（N，E，S，W）。

第2+M行：一个整数K。(1<=k<=10,000)    

第3+M..2+M+K:每行表示一个问题，包含两个整数代表两个农场。

输出

第1..K行：对应每个问题，输出单独的一个整数给出正确的距离。

样例输入

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

样例输出

13 3 36

提示

农场2 到6 有 20+3+13=36 的距离。

           F1 --- (13) ---- F6 --- (9) ----- F3

            |                                 |

           (3)                                |

            |                                (7)

           F4 --- (20) -------- F2            |

            |                                 |

           (2)                               F5

            | 

           F7 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
  
int gi()
{
    int str=0;char ch=getchar();
    while(ch>'9' || ch<'0')ch=getchar();
    while(ch>='0' && ch<='9')
    {
        str=str*10+ch-'0';
        ch=getchar();
    }
    return str;
}
  
const int N=40005;const int K=10005;
int num=0;
int fa[N];int dis[N];
int head[40005];bool d[N];
int number=0;int ans[N];
int header[40005];
struct Lin
{
    int next,to,dis;
}a[N*2];
  
struct LIN
{
    int next,to,id;
}b[N*2];
  
void init(int x,int y,int z)
{
    a[++num].next=head[x];
    a[num].to=y;
    a[num].dis=z;
    head[x]=num;
}
  
void init2(int x,int y,int jk)
{
    b[++number].next=header[x];
    b[number].to=y;
    b[number].id=jk;
    header[x]=number;
}
  
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
  
void dfs(int x)
{
    d[x]=1;
    int u;int lca;int ppap;
    for(int i=header[x]; i ;i=b[i].next)
    {
        u=b[i].to;
        if(d[u])
        {
            ppap=b[i].id;
            lca=find(u);
            ans[ppap]=dis[u]+dis[x]-2*dis[lca];
        }
    }
     
    for(int i=head[x]; i ;i=a[i].next)
    {
        u=a[i].to;
        if(!d[u])
        {
            dis[u]=dis[x]+a[i].dis;
            dfs(u);
            fa[u]=x;
        }
    }
}
  
int main()
{
    int n,m;
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
     
    while(m--)
    {
        x=gi();y=gi();z=gi();
        getchar();
        init(x,y,z);init(y,x,z);
    }
    int k=gi();
    for(int i=1;i<=k;i++)
    {
        x=gi();y=gi();
        init2(x,y,i);init2(y,x,i); 
    }
    dfs(1);
    for(int i=1;i<=k;i++)
        printf("%d
",ans[i]);
    return 0;
}