记录编号	499028	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2018-06-28 17:18:36	内存使用	25.53 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
int n,m,N;
struct P
{
	int u,v,w;
};
vector<P> e[40002];
int fa[40001],deep[40011];
bool vis[40001];
int grand[40001][80],gx[40001][80];
void build(int r)
{
	for (int i = 1; i <= N; ++i)
	{
		grand[r][i] = grand[grand[r][i-1]][i-1];
		gx[r][i] = gx[r][i-1]+gx[grand[r][i-1]][i-1];	
	}
	for (int i = 0; i < e[r].size(); ++i)
	{
		int t = e[r][i].v;
		if (grand[r][0] != t)
		{
			deep[t] = deep[r]+1;
			
			gx[t][0] = e[r][i].w;
			grand[t][0] = r;
			build(t);
			/* code */
		}
	}
	
}
int lca(int x,int y)
{
	if (deep[x] > deep[y])
	{
		swap(x,y);
	}
	int ans = 0;
	for (int i = N; i >= 0; --i)
	{
		if (deep[x] < deep[y]&&deep[grand[y][i]] >= deep[x])
		{
			ans += gx[y][i];y = grand[y][i];
		}
	}
	for (int i = N; i >= 0; --i)
	{
		if (grand[x][i] != grand[y][i])
		{
			ans += gx[x][i];
			ans+= gx[y][i];
			x = grand[x][i] ;
			y = grand[y][i];
			
		}
	}
	if (x!=y)
	{
		ans += gx[x][0];ans += gx[y][0];
	}
	return ans;
}
int main()
{
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	cin >> n >> m ;
	N = floor(log(n + 0.0) / log(2.0));
	for (int i = 1; i < n; ++i)
	{
		int t1,t2,t3;
		cin >> t1 >> t2 >> t3;
		P a={t1,t2,t3},b={t2,t1,t3};
		e[t1].push_back(a);
		e[t2].push_back(b);
	}
	build(1);
	for (int i = 0; i < m; ++i)
	{
		int t1,t2;
		cin >> t1 >> t2;
		cout << lca(t1,t2) << endl;
	}
	return 0;
}