记录编号	307091	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	小明	是否通过	通过
代码语言	C++	运行时间	1.715 s
提交时间	2016-09-13 19:34:02	内存使用	25.67 MiB

#include<stdio.h>
#include<cstring>
#include<cmath>
using namespace std;
int i,j;
int n,m;
int x=1,h[100010];//前向星
int blx[200020],blxd[200020];//遍历序
long long deep[100010],swz[100010],tdw[100010];//点信息
int y=0;//当前深度
int z=0;//当前遍历位置
long long ww=0;//当前价值
int k[200020][30];//区间信息
int x1,x2,nn;//lca节点
struct edge
{
	int to;
	int next;
	int w;
	edge()
	{
		next=-1;
	}
}A[100010];
void jt()
{
	int a1,a2,aw;
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&a1,&a2,&aw);
		A[i].to=a2;
		A[i].w=aw;
		A[i].next=h[a1];
		h[a1]=x++;
	}
}
void dfs(int v)
{
	y++;
	z++;
	deep[v]=y;
	tdw[v]=ww;
	swz[v]=z;
	blx[z]=v;
	blxd[z]=deep[v];
	for(int i=h[v];i!=-1;i=A[i].next)
	{
		ww+=A[i].w;
		dfs(A[i].to);
		z++;
		blx[z]=v;
		blxd[z]=deep[v];
		ww-=A[i].w;
	}
	y--;
}
void rmq()
{
	for(i=1;(i+(1<<j)-1)<=(n*2-1);i++)
		k[i][0]=blx[i];
	for(j=1;(1<<j)<=(n*2-1);j++)
		for(i=1;(i+(1<<j)-1)<=(n*2-1);i++)
		{
			if(deep[k[i][j-1]]>deep[k[i+(1<<(j-1))][j-1]])
				k[i][j]=k[i+(1<<(j-1))][j-1];
			else
				k[i][j]=k[i][j-1];
		}
}
void lca(int z1,int z2)
{
	int a,b;
	if(swz[z1]>swz[z2])
	{
		a=swz[z2];
		b=swz[z1];
	}
	else
	{
		a=swz[z1];
		b=swz[z2];
	}
	int r=log2(b-a+1);
	int xx;
	if(deep[k[a][r]]>deep[k[b-(1<<r)+1][r]])
		xx=k[b-(1<<r)+1][r];
	else 
		xx=k[a][r];
	printf("%lld\n",tdw[z2]+tdw[z1]-2*tdw[xx]);
}
void solve()
{
	scanf("%d",&nn);
	while(nn--)
	{
		scanf("%d%d",&x1,&x2);
		lca(x1,x2);
	}
}
int main()
{
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	memset(h,-1,sizeof(h));
	jt();
	dfs(1);
	rmq();
	solve();
	return 0;
}