记录编号	263371	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	1.027 s
提交时间	2016-05-24 20:33:46	内存使用	3.56 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

int n,m,i,a,b,c,k;
char qq,ww;
int fl[40010],f[40010];   //到父亲节点距离和父亲节点 
int s[40010],d[40010],zj[40010];   //存放节点和一个指针
int fa[40010];
bool v[40010];
vector <int> l[40010],ll[40010];   //l,ll存初始图
vector <int> son[40010];   //son存子节点
vector <int> w[40010];     //存放询问的节点
vector <int> ans[40010];   //存放询问的节点的答案

inline void maketree(int x){
	int i=0;
	v[x]=1;
	for (i=0;i<=l[x].size()-1;i++)
		if (not v[l[x][i]]){
			son[x].push_back(l[x][i]);	f[l[x][i]]=x;
			fl[l[x][i]]=ll[x][i];	maketree(l[x][i]);}
	return;
}   //DFS建树

inline int read(){
	int x=0,p=0;
	while (p-48<0||p-48>9)	p=getchar();
	while (p-48>=0&&p-48<=9)	{x=x*10+p-48;	p=getchar();}
	return x;
}   //快速读入

inline int find(int x){return (x==fa[x])?x:fa[x]=find(fa[x]);} 

inline int query(int a,int b,int lca){
	int an=0,q=0,e=0;
	q=a;	e=b;
	while (q!=lca)	an+=fl[q],q=f[q];
	while (e!=lca)	an+=fl[e],e=f[e];
	return an;
}   //计算树上两点间距离

inline void tarjan(int p){
	int i;
	if (son[p].size()!=0)
		for (i=0;i<=son[p].size()-1;i++)
		if (not v[son[p][i]]) {
			tarjan(son[p][i]);	fa[son[p][i]]=p;}
	v[p]=1;
	if (w[p].size()!=0)
	for (i=0;i<=w[p].size()-1;i++)
	if (v[w[p][i]])	ans[p][i]=query(p,w[p][i],find(w[p][i]));
	return;
}   //Tarjan求LCA

void work(){
	int i,q,e;
	k=read();
	for (i=1;i<=k;i++){
		s[i]=read();	d[i]=read();
		w[s[i]].push_back(d[i]);	w[d[i]].push_back(s[i]);
		ans[s[i]].push_back(0);	ans[d[i]].push_back(0);}
	memset(v,0,sizeof(v));
	for (i=1;i<=n;i++)	fa[i]=i;
	tarjan(1);
	for (i=1;i<=k;i++){
	if (ans[s[i]][zj[s[i]]]!=0)	printf("%d\n",ans[s[i]][zj[s[i]]]);
	else printf("%d\n",ans[d[i]][zj[d[i]]]);
	zj[s[i]]++;	zj[d[i]]++;}
	return;
}

int main(){
	freopen("dquery.in","r",stdin);
	freopen("dquery.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++){
		scanf("%d%d%d%c%c",&a,&b,&c,&qq,&ww);
		l[a].push_back(b);	ll[a].push_back(c);
		l[b].push_back(a);	ll[b].push_back(c);}
	for (i=1;i<=n;i++)	f[i]=i;
	maketree(1);   //建树 
	work();	
	return 0;
}