记录编号	305387	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.581 s
提交时间	2016-09-10 20:12:55	内存使用	3.98 MiB

#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=101000;
struct Edge{
	int next,to,dis,from;
}e[maxn];
int a[maxn];
int n,m,deep[maxn],size[maxn],top[maxn],root[maxn],son[maxn];
int id[maxn],pos[maxn],cnt,len,head[maxn],v[maxn];
void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].from=x;e[len].next=head[x];e[len].dis=z;head[x]=len;
}
void Dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(j!=root[x]){
			root[j]=x;v[j]=e[i].dis;
			deep[j]=deep[x]+1;
			Dfs1(j);
			size[x]+=size[j];
			if(size[j]>size[son[x]])son[x]=j;
		}
	}
}
void Dfs2(int x,int tp){
	top[x]=tp;id[x]=++cnt;pos[cnt]=x;
	if(son[x])Dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(son[x]!=j && root[x]!=j)Dfs2(j,j); 
	}
}
void Build(int rt,int l,int r){
	if(l==r){
	    a[rt]=v[pos[l]];return;
	}
	int mid=(l+r)>>1;
	Build(lson);Build(rson);
	a[rt]=a[rt<<1]+a[rt<<1|1];
}
int Get_query(int s,int t,int rt,int l,int r){
	if(s<=l && t>=r)return a[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return Get_query(s,t,lson);
	if(s>mid)return Get_query(s,t,rson);
	return  Get_query(s,t,lson)+Get_query(s,t,rson);
}
int tree_query(int x,int y){
	int fx=top[x],fy=top[y],ans=0;
	while(fx!=fy){
		if(deep[fx]<deep[fy]){swap(fx,fy);swap(x,y);}
		ans+=Get_query(id[fx],id[x],1,1,n);
		x=root[fx];fx=top[x];
	}
	if(deep[x]>deep[y])swap(x,y);
	if(id[x]+1<=id[y])ans+=Get_query(id[x]+1,id[y],1,1,n);
	return ans;
}
void Init();

int main(){
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
    Init();
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);Insert(y,x,z);
	}
	deep[1]=1;
	Dfs1(1);Dfs2(1,1);Build(1,1,n);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		//if(x==y){printf("0\n");continue;}
		printf("%d\n",max(tree_query(x,y),tree_query(y,x)));
	}
}