记录编号	349636	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	Hexฏ๎๎๎๎๎๎๎๎๎ۣۣۣ	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2016-11-15 09:06:43	内存使用	7.33 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define Size 1010

void read(int &p){
	p=0;
	char c;
	c=getchar();
	while( c < '0' || c > '9' )
	  c=getchar();
	while(  c>= '0' && c <= '9' )
	  {
	  	p=p*10+c-'0';
		c=getchar();
	  }
}

int n,q;
int f[Size],fa[Size],w[Size],ww[Size];
bool v[Size];
int l[Size][Size],lca[Size][Size];
vector<int> b[Size],son[Size];

void built(int x){
	int i,j,k;
	v[x]=true;
	if( b[x].size() == 0 )
	  return ;
	for(int i=0;i<=b[x].size()-1;i++)
	  if( !v[b[x][i]] )
	    {
	      f[b[x][i]]=x;
	      son[x].push_back(b[x][i]);
	      built(b[x][i]);
		}
	return ;
}

void Init(){
	for(int i=1;i<=n;i++)
	  {
	  	b[i].clear();
	  	v[i]=false;
	  	fa[i]=i;
	  }
	return ;
}

int find(int x){
	if( fa[x] == x )
	  return x;
	return find(fa[x]);
}

void tarjan(int x){
	if( son[x].size() != 0 )
	  {
	  	for(int i=0;i<son[x].size();i++)
	  	  if( !v[son[x][i]] )
	  	    {
	  	    	tarjan(son[x][i]);
	  	    	fa[son[x][i]]=x;
			}
	  }
	v[x]=true;
	if( b[x].size() != 0 )
	  for(int i=0;i<b[x].size();i++)
	    if( v[b[x][i]] )
	      {
	      	lca[x][b[x][i]]=find(b[x][i]);
	      	lca[b[x][i]][x]=find(b[x][i]);
		  }
	return ;
}

void answer(int x,int y,int lc){
	int i,j,k,ans;
	i=x,ans=0;
	while( i != lc )
	  {
	  	ans+=l[i][f[i]];
	  	i=f[i];
	  }
	i=y;
	while( i != lc )
	  {
	  	ans+=l[i][f[i]];
	  	i=f[i];
	  }
	printf("%d\n",ans);
	return ;
}

int main(int argc,char ** argv){
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	read(n);
	read(q);
	for(int i=1,u,v;i<=n-1;i++)
	  {
	  	read(u),read(v);
	  	read(l[u][v]);
	  	l[v][u]=l[u][v];
	  	b[u].push_back(v);
	  	b[v].push_back(u);
	  }
	f[1]=1;
	built(1);
	Init();
	for(int i=1;i<=q;i++)
	  {
	  	read(w[i]),read(ww[i]);
	  	b[w[i]].push_back(ww[i]);
	  	b[ww[i]].push_back(w[i]);
	  }
	tarjan(1);
	
//	for(int i=1;i<=n;i++,cout<<endl)
//	  for(int j=0;j<son[i].size();j++)
//	    cout<<son[i][j]<<" ";
//	cout<<endl;

//	for(int i=1;i<=n;i++,cout<<endl)
//	  for(int j=1;j<=n;j++)
//	   cout<<l[i][j]<<" "; 

	for(int i=1;i<=q;i++)
	  answer(w[i],ww[i],lca[w[i]][ww[i]]);
	return 0;
}