记录编号	269661	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.465 s
提交时间	2016-06-13 20:30:23	内存使用	36.86 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,d;
	node(){
		son.push_back(0);
		d.push_back(0);
	}
	void addson(int x,int dis){
		son.push_back(x);
		d.push_back(dis);
		son[0]++;
	}
}a[maxn];
void bfs(int);
void dfs(int,int);
void insert(int,int,int);
int dis(int,int);
int LCA(int,int);
void RMQ_init(const int*,int);
int RMQ_min(int,int);
int RMQ_minpos(int,int);
edge* last[maxn];
int len=0;
int depth[maxn<<1],b[maxn<<1],first[maxn],tim;
int mn[maxn<<1][18],pos[maxn<<1][18];
int dist[maxn];
bool vis[maxn]={false};
int n,m,x,y,z;
int main(){
#define MINE
#ifdef MINE
	freopen("dquery.in","r",stdin);
	freopen("dquery.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);
		scanf("%*[^0-9]");
	}
	bfs(1);
	dfs(1,1);
	RMQ_init(depth,(n<<1)-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);
	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;
			a[x].addson(y,e->dis);
			q.push(y);
		}
	}
}
inline void dfs(int x,int d){
	first[x]=++tim;
	b[tim]=x;
	depth[tim]=d;
	for(int i=1,y;i<=a[x].son[0];i++){
		y=a[x].son[i];
		dist[y]=dist[x]+a[x].d[i];
		dfs(y,d+1);
		b[++tim]=x;
		depth[tim]=d;
	}
}
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){
	return b[RMQ_minpos(first[x],first[y])];
}
inline void RMQ_init(const int* a,int n){
	for(int i=1;i<=n;i++){
		mn[i][0]=a[i];
		pos[i][0]=i;
	}
	for(int j=1;(1<<j)<=n;j++)for(int i=1;i<=n;i++){
		if(mn[i][j-1]<mn[i+(1<<(j-1))][j-1]){
			mn[i][j]=mn[i][j-1];
			pos[i][j]=pos[i][j-1];
		}
		else{
			mn[i][j]=mn[i+(1<<(j-1))][j-1];
			pos[i][j]=pos[i+(1<<(j-1))][j-1];
		}
	}
}
inline int RMQ_min(int l,int r){
	if(l>r)swap(l,r);
	int k=(int)log2(r-l+1);
	return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
inline int RMQ_minpos(int l,int r){
	if(l>r)swap(l,r);
	int k=(int)log2(r-l+1);
	if(mn[l][k]<mn[r-(1<<k)+1][k])return pos[l][k];
	else return pos[r-(1<<k)+1][k];
}
/*
7 6
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
3
1 6
1 4
2 6
*/