题意：给定一个树（10^5），m个询问（10^5），每次给定a，b，c，d，在区间[a，b]中选一个点，[c，d]选一个点，使得这两个点距离最大，输出最大距离。
题解：首先，我们有一个结论：对于一个集合的直径，如果我们将这个集合分解成两个非空集合，它的端点一定在两个非空集合的两个端这4个端点中。这非常的显然。。。
那么我们就可以做到合并两个集合，我们就可以用线段树维护每个区间的直径，就好啦，完全不用复杂的数据结构。
这道题卡时间，所以LCA要用欧拉序RMQ做。
复杂度O（nlogn）
#include<bits/stdc++.h>
using namespace std;
#define N 200005
inline int read(){
int x=,f=; char a=getchar();
while(a<'' || a>'') {if(a=='-') f=-; a=getchar();}
while(a>='' && a<='') x=x*+a-'',a=getchar();
return x*f;
}
int n,m,cnt=,euler[*N],dep[N],head[N],fi[N],dis[N],st[N][],mn[N][],Log[*N];
struct edges{
int to,c,next;
}e[N];
struct node{
int x1,x2,l,r;
}seg[*N];
struct data{
int x1,x2;
};
inline int getdis(int u,int v){
if(!u || !v) return ;
u=fi[u]; v=fi[v];
if(u>v) swap(u,v);
int p,len=Log[v-u+];
p=mn[u][len]<mn[v-(<<len)+][len]?st[u][len]:st[v-(<<len)+][len];
return dis[euler[u]]+dis[euler[v]]-*dis[p];
}
inline void update(int x){
int mx=,x1=seg[x<<].x1,x2=seg[x<<].x2,x3=seg[x<<|].x1,x4=seg[x<<|].x2,f;
if((f=getdis(x1,x2))>mx) seg[x].x1=x1,seg[x].x2=x2,mx=f; if((f=getdis(x1,x3))>mx) seg[x].x1=x1,seg[x].x2=x3,mx=f;
if((f=getdis(x1,x4))>mx) seg[x].x1=x1,seg[x].x2=x4,mx=f; if((f=getdis(x2,x3))>mx) seg[x].x1=x2,seg[x].x2=x3,mx=f;
if((f=getdis(x2,x4))>mx) seg[x].x1=x2,seg[x].x2=x4,mx=f; if((f=getdis(x3,x4))>mx) seg[x].x1=x3,seg[x].x2=x4,mx=f;
}
inline void insert(){
int u=read(),v=read(),c=read();
e[++cnt]=(edges){v,c,head[u]};head[u]=cnt;
}
void dfs(int x,int fa){
dep[x]=dep[fa]+; fi[x]=euler[]+;
for(int i=head[x];i;i=e[i].next){
if(fa==e[i].to) continue;
euler[++euler[]]=x;
dis[e[i].to]=dis[x]+e[i].c; dfs(e[i].to,x);
}
euler[++euler[]]=x;
}
inline void rmq_pre(){
for(int i=;i<=euler[];i++) st[i][]=euler[i],mn[i][]=dep[euler[i]];
for(int i=;i<=;i++)
for(int j=;j<=euler[];j++){
if(j+(<<i)->euler[]) break;
if(mn[j][i-]<mn[j+(<<(i-))][i-]) st[j][i]=st[j][i-],mn[j][i]=mn[j][i-];
else st[j][i]=st[j+(<<(i-))][i-],mn[j][i]=mn[j+(<<(i-))][i-];
}
Log[]=-; for(int i=;i<=euler[];i++) Log[i]=Log[i>>]+;
}
void build(int l,int r,int x){
seg[x].l=l; seg[x].r=r;
if(l==r) {seg[x].x1=l; seg[x].x2=; return;}
int mid=(l+r)>>;
build(l,mid,x<<);
build(mid+,r,x<<|);
update(x);
}
data merge(data tmp1,data tmp2){
int f,mx=,x1=tmp1.x1,x2=tmp1.x2,x3=tmp2.x1,x4=tmp2.x2;
data ret;
if((f=getdis(x1,x2))>mx) ret.x1=x1,ret.x2=x2,mx=f; if((f=getdis(x1,x3))>mx) ret.x1=x1,ret.x2=x3,mx=f;
if((f=getdis(x1,x4))>mx) ret.x1=x1,ret.x2=x4,mx=f; if((f=getdis(x2,x3))>mx) ret.x1=x2,ret.x2=x3,mx=f;
if((f=getdis(x2,x4))>mx) ret.x1=x2,ret.x2=x4,mx=f; if((f=getdis(x3,x4))>mx) ret.x1=x3,ret.x2=x4,mx=f;
return ret;
}
data query(int L,int R,int x){
int l=seg[x].l,r=seg[x].r;
if(l==L && r==R) {return (data){seg[x].x1,seg[x].x2};}
int mid=(l+r)>>;
if(R<=mid) return query(L,R,x<<);
else if(mid<L) return query(L,R,x<<|);
else return merge(query(L,mid,x<<),query(mid+,R,x<<|));
}
int main(){
n=read();
for(int i=;i<n;i++) insert();
dfs(,); rmq_pre(); build(,n,);
m=read();
while(m--){
int t1,t2,a=read(),b=read(),c=read(),d=read();
data tmp1=query(a,b,),tmp2=query(c,d,);
t1=max(getdis(tmp1.x1,tmp2.x1),getdis(tmp1.x1,tmp2.x2));
t2=max(getdis(tmp1.x2,tmp2.x1),getdis(tmp1.x2,tmp2.x2));
printf("%d\n",max(t1,t2));
}
return ;
}