记录编号	138354	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	RP++	是否通过	通过
代码语言	C++	运行时间	0.204 s
提交时间	2014-11-05 20:30:28	内存使用	7.85 MiB

#include<cstdio>
using namespace std;
struct node{
	int to;
	int next;
	int val;
}f[100000];
int head[40001];
int deep[40010];
int father[40010][20];
int ans[40010][20];
int tot=0;
int nPoint,nEdge;
inline void dfs(int ind)
{
	for(int i=head[ind];i;i=f[i].next)
	{
		int l=f[i].to;
		if(!deep[l])
		{
			deep[l]=deep[ind]+1;
			father[l][0]=ind;
			ans[l][0]=f[i].val;
			dfs(l);
		}
	}
}
inline int readint()
{
	char ch=getchar();
	while(ch<48||ch>57)ch=getchar();
	int x=0;
	while(ch>=48&&ch<=57)
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
int buf[10];
inline void writeint(int i)
{
	buf[0]=0;
	int p=0;
	if(i==0)p++;
	else while(i)
		 {
				buf[p++]=i%10;
				i/=10;
		 }
	for(int j=p-1;j>=0;j--)putchar('0'+buf[j]);
}
inline void Build(int s,int t,int val)
{
	f[++tot].to=t;
	f[tot].next=head[s];
	f[tot].val=val;
	head[s]=tot;
}
inline void Swap(int &x,int &y)
{
	x^=y;
	y^=x;
	x^=y;
}
inline int Query(int x,int y)
{
	if(deep[x]<deep[y])Swap(x,y);
	int i;
	for(i=0;(1<<i)<=deep[x];i++);
	i--;
	int res=0;
	for(int j=i;j>=0;j--)
	{
		if(deep[x]-(1<<j)>=deep[y])
		{
			res+=ans[x][j];
			x=father[x][j];
		}
	}
	if(x==y)return res;
	for(int j=i;j>=0;j--)
	{
		if(father[x][j]!=father[y][j])
		{
			res+=ans[x][j]+ans[y][j];
			x=father[x][j];
			y=father[y][j];
		}
	}
	res+=ans[x][0]+ans[y][0];
	return res;
}
int main()
{
    freopen("dquery.in","r",stdin);
	freopen("dquery.out","w",stdout);
	int nPoint=readint(),nEdge=readint();
	int s,t,val;
	char ch;
	for(int i=1;i<=nEdge;i++)
	{
		s=readint(),t=readint(),val=readint();
		Build(s,t,val);
		Build(t,s,val);
		ch=getchar(),ch=getchar();
	}
	deep[1]=1;
	dfs(1);
	for(int j=1;(1<<j)<=nPoint;j++)
	{
		for(int i=1;i<=nPoint;i++)
		{
			ans[i][j]=ans[i][j-1]+ans[father[i][j-1]][j-1];
			father[i][j]=father[father[i][j-1]][j-1];
		}
	}
	int nQue=readint();
	int x,y;
	for(int i=1;i<=nQue;i++)
	{
		x=readint(),y=readint();
		writeint(Query(x,y));
		putchar('\n');
 	}
}