记录编号	173506	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.207 s
提交时间	2015-07-28 21:51:42	内存使用	7.87 MiB

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstdlib>
using namespace std;
int fa[40002][20];
int f[40002][20];
int head[40002];
int deep[40002];
int p,ans,n,m,a,b,c,tot;
char s;
inline int in()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	return x;
}
struct dd
{
    int zhong;
    int juli;
    int next;
}jie[100002];
void add(int x,int y,int z)
{
     tot++;
     jie[tot].zhong=y;
     jie[tot].next=head[x];
     head[x]=tot;
     jie[tot].juli=z;
}
void dfs(int y)
{   
     for(int i=head[y];i;i=jie[i].next)
     {
         int yu=jie[i].zhong;
         if(!deep[yu])
         {
            deep[yu]=deep[y]+1;
            fa[yu][0]=y;
            f[yu][0]=jie[i].juli;
            dfs(yu);
         }
     }
}
//从网上摘下来的模板，包括初始化fa数组，更新2^j祖先，求lca； 
int LCA(int x,int y)
{   
    int i,j;
    if(deep[x]<deep[y])  swap(x,y);
    for(i=0;(1<<i)<=deep[x];i++);
    i--;
    for(j=i;j>=0;j--)
      if(deep[x]-(1<<j)>=deep[y])
       {  ans+=f[x][j];
          x=fa[x][j];
       }
    if(x==y) return ans;
    for(j=i;j>=0;j--)
    {
       if(fa[x][j]!=fa[y][j])
       {  ans+=f[x][j]+f[y][j];
          x=fa[x][j];
          y=fa[y][j];
          //答案加上边上的权值； 
       }
    }
    ans=ans+f[x][0]+f[y][0];//在上一步中，跳出循环，找到lca，但是离lca最近的那两条边权值还没加上； 
    return ans;
}
int main()
{   freopen("dquery.in","r",stdin);
	freopen("dquery.out","w",stdout);
    n=in(),m=in();
    deep[1]=1;
    for(int i=1;i<=m;++i)
    {
        a=in();
        b=in();
        c=in();
        add(a,b,c);
        add(b,a,c);
        s=getchar(),s=getchar();
    } 
    dfs(1);
    for(int j=1;(1<<j)<=n;++j)
      for(int i=1;i<=n;++i)
     {
             fa[i][j]=fa[fa[i][j-1]][j-1];
             f[i][j]=f[i][j-1]+f[fa[i][j-1]][j-1];
     }
    p=in();
    int g,h;
    for(int i=1;i<=p;++i)
    {  ans=0;
       g=in();
       h=in();
       int yu=LCA(g,h);
       printf("%d\n",yu);
    }
    //while(1);
    return 0;
}