记录编号	306352	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	0.340 s
提交时间	2016-09-11 20:54:07	内存使用	2.16 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#define pb push_back
using namespace std;
const int nmax=20086;
const int vmax=20;
int n,m,q,s=0;
int tmpu,tmpv,tmpdis;
int tmpl,tmpr;
int dtr[nmax];
int list[nmax],deep[nmax];
int pos[nmax];
int smin[nmax][vmax];
bool vis[nmax];
class edge
{
public:
	int u,v;
	int dis;
};
vector<edge> edges;
vector<int > G[nmax];
void PreDo()
{
	scanf("%d%d",&n,&q);
	dtr[n]=0;
	deep[0]=0;
	for(int i=1;i<=n-1;i++)
	{
		dtr[i]=0;
		scanf("%d%d%d",&tmpu,&tmpv,&tmpdis);
		edges.pb((edge){tmpu,tmpv,tmpdis});
		G[tmpu].pb(edges.size()-1);
		edges.pb((edge){tmpv,tmpu,tmpdis});
		G[tmpv].pb(edges.size()-1);
	}
}
void DFS(int x)
{
	s++;
	list[s]=x;
	pos[x]=s;
	vis[x]=1;
	for(int i=0;i<G[x].size();i++)
	{
		if(vis[edges[G[x][i]].v]==0)
		{
			deep[edges[G[x][i]].v]=deep[edges[G[x][i]].u]+1;
			dtr[edges[G[x][i]].v]=edges[G[x][i]].dis+dtr[x];
			DFS(edges[G[x][i]].v);
			s++;
			list[s]=x;
		}
	}
}
int minx(int a,int b)
{
	if(deep[a]>deep[b])
		return b;
	else
		return a;//fanle
}
void exchange(int &tmpl,int &tmpr)
{
	if(pos[tmpl]>pos[tmpr])
	{
		int tmp;
		tmp=tmpl;
		tmpl=tmpr;
		tmpr=tmp;
	}
}
void RMQ()
{
	for(int i=1;i<=s;i++)
		smin[i][0]=list[i];
	for(int j=1;j<vmax;j++)
		for(int i=1;i<=s;i++)
			if(i+(1<<j)-1<=s)
				smin[i][j]=minx(smin[i][j-1],smin[i+(1<<(j-1))][j-1]);

}
int main()
{
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	PreDo();
	DFS(1);
	RMQ();
	//for(int i=1;i<=s;i++)
		//printf("%d ",list[i]);
	//scanf("%d",&q);
	/*for(int j=0;j<1;j++)
	{
		for(int i=1;i<=s;i++)
			printf("%d ",smin[i][j]);
		printf("\n");
	}
	*/
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&tmpl,&tmpr);
		exchange(tmpl,tmpr);
		int k=int(floor(log2(pos[tmpr]-pos[tmpl]+1)));//pos[]HIGHLIGHT
		int LCA=minx(smin[pos[tmpl]][k],smin[pos[tmpr]-(1<<k)+1][k]);
		//printf("%d\n",LCA);
		//printf("%d %d\n",k,pos[tmpr]-(1<<k)+1);
		printf("%d\n",dtr[tmpl]+dtr[tmpr]-2*dtr[LCA]);
	}
	/*for(int i=1;i<=n;i++)
		printf("%d ",pos[i]);
	printf("\n");
	for(int i=1;i<=s;i++)
		printf("%d ",list[i]);
	printf("\n");
	for(int i=1;i<=s;i++)
		printf("%d ",deep[list[i]]);
	//for(int i=1;i<=n;i++)
		//printf("%d ",deep[i]);
	*/
	return 0;
}