路径交

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
 
typedef pair<int,int> P;
typedef long long ll;
const int INF=1e9;
const int maxn=500000+10; 

int cnt,head[maxn],nxt[maxn],to[maxn],c[maxn];
int p[2*maxn],fa[2*maxn][20],dep[2*maxn];
ll dis[2*maxn];
P sum[2*maxn];
int n,m;
int q1,q2;

void  add(int u,int v,int d)
{
	nxt[++cnt]=head[u];to[cnt]=v;head[u]=cnt;c[cnt]=d;
	nxt[++cnt]=head[v];to[cnt]=u;head[v]=cnt;c[cnt]=d;
}

void dfs(int u,int f)
{
	for (int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if (v==f) continue;
		dis[v]=dis[u]+c[i];
		dep[v]=dep[u]+1;
		fa[v][0]=u;
		dfs(v,u);
	}
}

void _lca(){
	for (int j=1;(1<<j)<=n;j++)
	for  (int i=1;i<=n;i++)
	 fa[i][j]=fa[fa[i][j-1]][j-1]; 
}

int lca(int a,int b){
	if (dep[a]<dep[b]) swap(a,b);
	int f=dep[a]-dep[b];
	for (int j=0;(1<<j)<=f;j++)
	  if ((1<<j)&f) a=fa[a][j];
	  
	if (a!=b)
	{
	 	for (int j=log2(n)+1;j>=0;j--)
	      { if (fa[a][j]!=fa[b][j])
	          a=fa[a][j],b=fa[b][j];
		  }
	  a=fa[a][0]; //少了这样一句话
	} 
	return a;
}

bool cmp(int a,int b){
	return dep[a]>dep[b];
}

P unit(P t1,P t2){
	int a[10];
	a[0]=lca(t1.first,t2.first);
	a[1]=lca(t1.first,t2.second);
	a[2]=lca(t1.second,t2.first);
	a[3]=lca(t1.second,t2.second);
	sort(a,a+4,cmp);
	return P(a[0],a[1]);
}

void build(int rt,int l,int r){
   if(l==r) 
      {
      	scanf("%d%d",&sum[rt].first,&sum[rt].second);
	    return;
	  }
	int m=(l+r)/2;
	build(rt<<1,l,m);   //此处rt<<1忘记打wa了
	build(rt<<1|1,m+1,r); 
    sum[rt]=unit(sum[rt<<1],sum[rt<<1|1]);
}
P query(int rt,int l,int r){
	if (q1<=l&&q2>=r) return sum[rt];
	int m=(l+r)>>1;
    if (q2<=m) return query(rt<<1,l,m);
	else if (q1>m) return query(rt<<1|1,m+1,r); 
    else return unit(query(rt<<1,l,m),query(rt<<1|1,m+1,r));
}


int main()
{
    scanf("%d",&n);
    for (int i=1;i<n;i++)
     {
     	int u,v,d;
     	scanf("%d%d%d",&u,&v,&d);
     	add(u,v,d);
	 }
	 dfs(1,1);
	 _lca();
	 scanf("%d",&m);
	 build(1,1,m);
	 
	 int kase;scanf("%d",&kase);
	 while (kase--){
	 	scanf("%d%d",&q1,&q2);
		 P a=query(1,1,m);
		 ll ans=dis[a.first]+dis[a.second]-2*dis[lca(a.first,a.second)];
		 printf("%lld\n",ans); 
	 } 
  return 0;
}