记录编号	96542	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.136 s
提交时间	2014-04-13 22:11:21	内存使用	7.03 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=40010,SIZELOG=20;
int N,M,S;
vector<pair<int,int> > c[SIZEN];
int grand[SIZEN][SIZELOG]={0},gdis[SIZEN][SIZELOG]={0};
int depth[SIZEN]={0};
int LCAdis(int a,int b){//a和b的距离
	if(depth[a]>depth[b]) swap(a,b);//a在上面b在下面
	//上下不能弄反
	int ans=0;
	for(int i=S;i>=0;i--) if(depth[a]<depth[b]&&depth[grand[b][i]]>=depth[a]) ans+=gdis[b][i],b=grand[b][i];
	for(int i=S;i>=0;i--) if(grand[a][i]!=grand[b][i]) ans+=gdis[a][i],ans+=gdis[b][i],a=grand[a][i],b=grand[b][i];
	if(a!=b) ans+=gdis[a][0],ans+=gdis[b][0];//现在a和b再往上走一步就是LCA了
	//否则它们就是LCA,这个if不加会错
	return ans;
}
void DFS(int x){
	for(int i=1;i<=S;i++){
		grand[x][i]=grand[grand[x][i-1]][i-1];
		gdis[x][i]=gdis[x][i-1]+gdis[grand[x][i-1]][i-1];
		if(!grand[x][i]) break;
	}
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i].first;
		if(u!=grand[x][0]){
			depth[u]=depth[x]+1;
			grand[u][0]=x,gdis[u][0]=c[x][i].second;
			DFS(u);
		}
	}
}
void work(void){
	int Q,a,b;
	scanf("%d",&Q);
	while(Q--){
		scanf("%d%d",&a,&b);
		printf("%d\n",LCAdis(a,b));
	}
}
void read(void){
	scanf("%d%d",&N,&M);
	S=floor(log(N+0.0)/log(2.0));
	int F1,F2,L;
	char D;
	for(int i=1;i<=M;i++){
		scanf("%d %d %d %c\n",&F1,&F2,&L,&D);
		c[F1].push_back(make_pair(F2,L));
		c[F2].push_back(make_pair(F1,L));
	}
}
int main(){
	freopen("dquery.in","r",stdin);
	freopen("dquery.out","w",stdout);
	read();
	depth[0]=-1;//否则会错
	DFS(1);
	work();
	return 0;
}