像树的直径一样,两个集合的最长路也是由两个集合内部的最长路的两个端点组成的,于是我们知道了两个集合的最长路,枚举一下两两端点算出答案就可以合并了,所以就可以用线段树维护一个区间里的最长路了。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=,inf=1e9;
struct tjm{int too,dis,pre;}e[maxn];
struct poi{int p[];ll dis;}tree[maxn<<];
int n,m,a,b,x,y,z,tot;
int d[maxn],son[maxn],size[maxn],fa[maxn],top[maxn],last[maxn];
ll dep[maxn];
inline void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
void add(int x,int y,int z){e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;}
void dfs1(int x)
{
size[x]=;d[x]=d[fa[x]]+;
for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)
if(too!=fa[x])
{
dep[too]=dep[x]+e[i].dis;
fa[too]=x;dfs1(too);
size[x]+=size[too];
if(size[too]>size[son[x]])son[x]=too;
}
}
void dfs2(int x,int tp)
{
top[x]=tp;
if(son[x])dfs2(son[x],tp);
for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)
if(too!=fa[x]&&too!=son[x])dfs2(too,too);
}
int lca(int x,int y)
{
int f1=top[x],f2=top[y];
while(f1!=f2)
{
if(d[f1]<d[f2])swap(x,y),swap(f1,f2);
x=fa[f1];f1=top[x];
}
if(d[x]<d[y])swap(x,y);
return y;
}
void pushup(poi x,poi y,ll &dist,int &p1,int &p2)
{
if(x.dis>y.dis)dist=x.dis,p1=x.p[],p2=x.p[];
else dist=y.dis,p1=y.p[],p2=y.p[];
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(x.p[i]&&y.p[j])
{
ll dis=dep[x.p[i]]+dep[y.p[j]]-(dep[lca(x.p[i],y.p[j])]<<);
if(dis>dist)dist=dis,p1=x.p[i],p2=y.p[j];
}
}
void build(int x,int l,int r)
{
if(l==r){tree[x].p[]=tree[x].p[]=l;return;}
int mid=(l+r)>>;
build(x<<,l,mid);build(x<<|,mid+,r);
pushup(tree[x<<],tree[x<<|],tree[x].dis,tree[x].p[],tree[x].p[]);
}
void query(int x,int l,int r,int cl,int cr,ll &dis,int &p1,int &p2)
{
if(cl<=l&&r<=cr){dis=tree[x].dis;p1=tree[x].p[];p2=tree[x].p[];return;}
int mid=(l+r)>>;
poi t1,t2;t1.dis=t2.dis=-;t1.p[]=t1.p[]=t2.p[]=t2.p[]=;
if(cl<=mid)query(x<<,l,mid,cl,cr,t1.dis,t1.p[],t1.p[]);
if(cr>mid)query(x<<|,mid+,r,cl,cr,t2.dis,t2.p[],t2.p[]);
pushup(t1,t2,dis,p1,p2);
}
int main()
{
read(n);
for(int i=;i<n;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);
dfs1();dfs2(,);
build(,,n);
read(m);
for(int i=;i<=m;i++)
{
read(a),read(b),read(x),read(y);
poi t1,t2;t1.dis=t2.dis=t1.p[]=t1.p[]=t2.p[]=t2.p[]=;ll dis;int p1,p2;
query(,,n,a,b,dis,t1.p[],t1.p[]);query(,,n,x,y,dis,t2.p[],t2.p[]);
pushup(t1,t2,dis,p1,p2);
printf("%lld\n",dis);
}
}