记录编号	201665	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	wmez	是否通过	通过
代码语言	C++	运行时间	1.001 s
提交时间	2015-10-31 06:26:46	内存使用	25.48 MiB

#include<cstdio>
#include<vector>
using namespace std;
#define mp make_pair
vector <pair<int,int> >edge[100005];
int fa[100005][31];
int dis[100005][31];
int deep[100005];
int n,q,x,y,z,m;
void DFS(int x)
{
	for(int i=0;i<edge[x].size();i++)
	{
		if(deep[edge[x][i].first])
		{
			continue;
		}
		deep[edge[x][i].first]=deep[x]+1;
		fa[edge[x][i].first][0]=x;
		dis[edge[x][i].first][0]=edge[x][i].second;
		DFS(edge[x][i].first);
	}
}
int LCA(int x,int y)
{
	if(deep[x]<deep[y])
	{
		x^=y^=x^=y;
	}
	int i;
	for(i=0;(1<<i)<=deep[x];i++);
	i--;
	int res=0;
	for(int j=i;~j;j--)
	{
		if(deep[x]-(1<<j)>=deep[y])
		{
			res+=dis[x][j];
			x=fa[x][j];
		}
	}
	if(x==y)
	{
		return res;
	}
	for(int j=i;~j;j--)
	{
		if(fa[x][j]!=fa[y][j])
		{
			res+=dis[x][j]+dis[y][j];
			x=fa[x][j];
			y=fa[y][j];
		}
	}
	res+=dis[x][0]+dis[y][0];
	return res;
}
int main()
{
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		edge[x].push_back(mp(y,z));
		edge[y].push_back(mp(x,z));
	}
	deep[1]=1;
	DFS(1);
	for(int j=1;(1<<j)<=n;j++)
	{
		for(int i=1;i<=n;i++)
		{
			dis[i][j]=dis[i][j-1]+dis[fa[i][j-1]][j-1];
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
}