Description

给定一棵$n$个点的树，以及$m$条路径，每次询问第$L$条到第$R$条路径的交集部分的长度（如果一条边同时出现在$2$条路径上，那么它属于路径的交集）。

Input

第一行一个数$n$$(n<=5\cdot 10^5)$

接下来$n-1$行，每行三个数$x,y,z$，表示一条从$x$到$y$并且长度为$z$的边
第$n+1$行一个数$m$$(m<=5\cdot 10^5)$

接下来$m$行，每行两个数$u,v$，表示一条从$u$到$v$的路径

接下来一行一个数$Q$，表示询问次数$(Q<=5\cdot 10^5)$

接下来$Q$行，每行两个数$L$和$R$

Output

$Q$行，每行一个数表示答案。

Sample Input

4
1 2 5
2 3 2
1 4 3
2
1 2
3 4
1
1 2

Sample Output

5

Solution

线段树维护路径交，树上两条路径$u1\leftrightarrow v1$和$u2\leftrightarrow v2$的交为$lca(u1,u2),lca(u1,v2),lca(v1,u2),lca(v1,v2)$这四个点中深度较深的两点之间的路径，在线倍增后按此合并即可，$u\leftrightarrow v$路径长度即为$u$到根的长度+$v$到路径的长度-$2\cdot\ lca(u,v)$到根的长度

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define maxn 500005
struct edge
{int v,w,next;
}g[2*maxn];
int tot,head[maxn];
void init()
{tot=0;memset(head,-1,sizeof(head));
}
void add(int u,int v,int w)
{g[tot].v=v,g[tot].w=w,g[tot].next=head[u],head[u]=tot++;
}
int Fa[maxn][21],Deep[maxn];
ll Dis[maxn];
void dfs(int u,int fa)
{Fa[u][0]=fa;for(int i=1;i<=20;i++)Fa[u][i]=Fa[Fa[u][i-1]][i-1];for(int i=head[u];~i;i=g[i].next){int v=g[i].v,w=g[i].w;if(v==fa)continue;Dis[v]=Dis[u]+w,Deep[v]=Deep[u]+1;dfs(v,u);}
}
int Lca(int u,int v)
{if(Deep[u]<Deep[v])swap(u,v);for(int i=20;i>=0;i--)if(Deep[Fa[u][i]]>=Deep[v])u=Fa[u][i];if(u==v)return u;for(int i=20;i>=0;i--)if(Fa[u][i]!=Fa[v][i])u=Fa[u][i],v=Fa[v][i];return Fa[u][0];
}
bool cmp(int a,int b)
{return Deep[a]>Deep[b];
}
P Unite(P x,P y)
{int a[4];a[0]=Lca(x.first,y.first),a[1]=Lca(x.first,y.second),a[2]=Lca(x.second,y.first),a[3]=Lca(x.second,y.second);sort(a,a+4,cmp);return P(a[0],a[1]);
}
#define ls (t<<1)
#define rs (t<<1|1)
P Path[maxn<<2];
void push_up(int t)
{Path[t]=Unite(Path[ls],Path[rs]);
}
void build(int l,int r,int t)
{if(l==r){scanf("%d%d",&Path[t].first,&Path[t].second);return ;}int mid=(l+r)/2;build(l,mid,ls),build(mid+1,r,rs);push_up(t);
}
P query(int L,int R,int l,int r,int t)
{if(L<=l&&r<=R)return Path[t];int mid=(l+r)/2;if(R<=mid)return query(L,R,l,mid,ls);else if(L>mid)return query(L,R,mid+1,r,rs);else return Unite(query(L,R,l,mid,ls),query(L,R,mid+1,r,rs));
}
int main()
{int n,m,q;scanf("%d",&n);init();for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w),add(v,u,w);}dfs(1,1);scanf("%d",&m);build(1,m,1);scanf("%d",&q);while(q--){int l,r;scanf("%d%d",&l,&r);P t=query(l,r,1,m,1);int u=t.first,v=t.second;ll ans=Dis[u]+Dis[v]-2ll*Dis[Lca(u,v)];printf("%lld\n",ans); }return 0;
}