记录编号	271121	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.942 s
提交时间	2016-06-15 17:32:11	内存使用	13.56 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100100;
struct edge{
	int to,dis;
	edge* prev;
	edge():to(0),dis(0),prev(NULL){}
}ee[maxn<<1];
struct node{
	vector<int>son;
	node(){
		son.push_back(0);
	}
	void addson(int x){
		son.push_back(x);
		son[0]++;
	}
}a[maxn];
void bfs(int);
void dfs(int,int);
void insert(int,int,int);
int dis(int,int);
int LCA(int,int);
edge* last[maxn];
int len=0;
int depth[maxn],dist[maxn];
int f[maxn][23]={{0}};
bool vis[maxn]={false};
int n,m,x,y,z;
int main(){
#define MINE
#ifdef MINE
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
#endif
	scanf("%d%*d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		insert(x,y,z);
		insert(y,x,z);
	}
	bfs(1);
	for(int j=1;j<=20;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&x,&y);
		printf("%d\n",dis(x,y));
	}
	return 0;
}
inline void bfs(int x){
	queue<int>q;
	q.push(x);
	dist[x]=0;
	depth[x]=1;
	while(!q.empty()){
		x=q.front();
		q.pop();
		vis[x]=true;
		for(edge* e=last[x];e;e=e->prev){
			int y=e->to;
			if(vis[y])continue;
			f[y][0]=x;
			dist[y]=dist[x]+e->dis;
			depth[y]=depth[x]+1;
			a[x].addson(y);
			q.push(y);
		}
	}
}
inline void insert(int x,int y,int z){
	ee[len].to=y;
	ee[len].dis=z;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
inline int dis(int x,int y){
	return dist[x]+dist[y]-(dist[LCA(x,y)]<<1);
}
inline int LCA(int x,int y){
	if(depth[x]<depth[y])swap(x,y);
	for(int j=20;j>=0;j--)if(depth[f[x][j]]>=depth[y])x=f[x][j];
	if(x==y)return x;
	if(f[x][0]==f[y][0])return f[x][0];
	for(int j=20;j>=0;j--)if(f[x][j]!=f[y][j]){
		x=f[x][j];
		y=f[y][j];
	}
	return f[x][0];
}