记录编号	471668	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	coolkid	是否通过	通过
代码语言	C++	运行时间	0.104 s
提交时间	2017-11-06 18:29:44	内存使用	7.95 MiB

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
 
const int MAXN=40010;
const int MAXLOG=20;
 
struct Edge{
	int from,to,dist,nxt;
}edges[MAXN<<1];
int head[MAXN],p=0;
 
void addedge(int f,int t,int d){
	edges[p].from=f;edges[p].to=t;edges[p].dist=d;edges[p].nxt=head[f];head[f]=p;p++;
}
 
int n,m,q;
int dep[MAXN],fa[MAXN][MAXLOG],faw[MAXN][MAXLOG];
 
void init(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int f,t,d;char s[5];
		scanf("%d%d%d%s",&f,&t,&d,s);
		addedge(f,t,d);
		addedge(t,f,d);
	}
}
 
void dfs(int u){
	for(int i=head[u];~i;i=edges[i].nxt){
		int v=edges[i].to,d=edges[i].dist;
		if(fa[u][0]==v) continue;
		fa[v][0]=u;faw[v][0]=d;dep[v]=dep[u]+1;
		dfs(v);
	}
}
 
int mxlg=0;
 
void Mk(){
	for(int i=MAXLOG;i>=0;i--) if(n&(1<<i)){ mxlg=i;break; }
	mxlg++;
	for(int j=1;j<=mxlg;j++)
		for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1],faw[i][j]=faw[fa[i][j-1]][j-1]+faw[i][j-1];
	
}
 
void Query(int u,int v){
	if(dep[v]>dep[u]) swap(u,v);
	int dlt=dep[u]-dep[v];
	int res=0;
	for(int i=mxlg;i>=0;i--) if(dlt&(1<<i)) res+=faw[u][i],u=fa[u][i];
	for(int i=mxlg;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			res+=(faw[u][i]+faw[v][i]);
			u=fa[u][i];v=fa[v][i];
		}
	}
	if(u==v){
		printf("%d\n",res);
		return;
	}
	printf("%d\n",faw[v][0]+faw[u][0]+res);
}
 
int main(){
	freopen("dquery.in","r",stdin);
	freopen("dquery.out","w",stdout);
	init();
	dfs(1);
	Mk();
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		Query(u,v);
	}
	return 0;
}