【题意】给定n个点的树，m次求[a,b]和[c,d]中各选出一个点的最大距离。abcd是标号区间，n,m<=10^5
【算法】LCA+树的直径理论+线段树
【题解】
树的直径性质：距离树上任意点最远的点一定是直径的一端。此结论在点集中依然试用。
那么根据性质，容易得到答案路径的两端一定是[a,b]直径的一端和[c,d]直径的一端的连线。
（考虑任意一个点集AB的点，在点集A中距离最远的是a或b，在点集B中距离最远的是c或d，故直径的端点只能是abcd）
从而，两个区间的直径可以快速合并成一个区间的直径，即直径的可并性。
因为直径可并和区间标号连续，所以可以用线段树维护一段区间的直径并查询。
连线用LCA解决，倍增常数较大会TLE，使用树链剖分或RMQ-LCA皆可。
复杂度O(n logn)。
【注意】
RMQ查询时注意判断l>r时swap。
线段树合并时要从左右子树内部取答案，而询问不能从内部取答案。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
int first[maxn],a[maxn*],b[maxn],logs[maxn*],d[maxn*][],p[maxn*][],deep[maxn],dis[maxn],tot,cnt;
int L[maxn*],R[maxn*],n,m;
struct edge{int v,w,from;}e[maxn*];
struct cyc{int num,A,B;}t[maxn*]; int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
void insert(int u,int v,int w){cnt++;e[cnt].v=v;e[cnt].w=w;e[cnt].from=first[u];first[u]=cnt;}
void dfs(int x,int fa){
a[++tot]=x;b[x]=tot;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
deep[e[i].v]=deep[x]+;
dis[e[i].v]=dis[x]+e[i].w;
dfs(e[i].v,x);
a[++tot]=x;
}
}
void RMQ_init(){
logs[]=-;for(int i=;i<=tot;i++)logs[i]=logs[i>>]+;
for(int i=;i<=tot;i++)d[i][]=deep[a[i]],p[i][]=i;
for(int j=;(<<j)<=tot;j++){
for(int i=;i+(<<j)-<=tot;i++)if(d[i][j-]<d[i+(<<(j-))][j-]){
d[i][j]=d[i][j-];p[i][j]=p[i][j-];
}else{d[i][j]=d[i+(<<(j-))][j-];p[i][j]=p[i+(<<(j-))][j-];}
}
}
int lca(int l,int r){
l=b[l],r=b[r];
if(l>r)swap(l,r);//
int k=logs[r-l+];
k=d[l][k]<d[r-(<<k)+][k]?p[l][k]:p[r-(<<k)+][k];
return dis[a[l]]+dis[a[r]]-*dis[a[k]];
}
cyc tr(bool ok,cyc L,cyc R){
cyc x=(cyc){-,,};
if(!ok){
if(L.A==)return R;
if(R.A==)return L;
x=L;
if(R.num>x.num)x=R;
}
int num=lca(L.A,R.A);
if(num>x.num)x=(cyc){num,L.A,R.A};
num=lca(L.A,R.B);
if(num>x.num)x=(cyc){num,L.A,R.B};
num=lca(L.B,R.A);
if(num>x.num)x=(cyc){num,L.B,R.A};
num=lca(L.B,R.B);
if(num>x.num)x=(cyc){num,L.B,R.B};
return x;
}
void build(int k,int l,int r){
L[k]=l;R[k]=r;
if(l==r)t[k]=(cyc){,l,r};
else{
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
t[k]=tr(,t[k<<],t[k<<|]);
}
}
cyc ask(int k,int l,int r){
if(l<=L[k]&&R[k]<=r)return t[k];
else{
int mid=(L[k]+R[k])>>;
cyc x=(cyc){,,};
if(l<=mid)x=ask(k<<,l,r);
if(r>mid)x=tr(,x,ask(k<<|,l,r));
return x;
}
}
int main(){
n=read();
for(int i=;i<n;i++){
int u=read(),v=read(),w=read();
insert(u,v,w);insert(v,u,w);
}
tot=;dfs(,);RMQ_init();build(,,n);
m=read();
for(int i=;i<=m;i++){
int x=read(),y=read(),z=read(),w=read();
cyc q=tr(,ask(,x,y),ask(,z,w));
printf("%d\n",q.num);
}
return ;
}