题干大意：

有一棵树，每次询问点集l1-r1与l2-r2之间的最大距离

蒟蒻用线段树维护的

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls pos<<1
#define rs pos<<1|1
const int N=1e6+10;
int n,q;
int h[N],ver[N*2],edge[N*2],ne[N*2],idx;
int dis[N];
void link( int u , int v , int w )
{
    ne[idx] = h[u] ;
    edge[idx] = w ;
    ver[idx] = v ;
    h[u] = idx++ ;
}
int fa[N],Size[N],son[N],dep[N];
void dfs1( int x , int f , int w )
{
	Size[x] = 1 ;
    dep[x] = dep[f] + 1 ;
    fa[x] = f ;
    son[x] = -1 ;
    dis[x] = dis[f] + w ;
    for( int i = h[x] ; ~i ; i = ne[i] )
    {
    	int y = ver[i] ;
    	if( y == f ) continue ;
    	dfs1( y , x , edge[i] ) ;
    	Size[x] += Size[y] ;
    	if( son[x]==-1 || Size[y] > Size[son[x]] ) son[x] = y ; // 重链 
	}
}
int rnk[N],dfn[N],top[N],T;
void dfs2( int x , int t )
{
  	dfn[x] = ++T ;
  	rnk[T] = x ;
  	top[x] = t ;
  	if( son[x] == -1 ) return ;
  	dfs2 (son[x] , t ) ; // 优先遍历重链
  	for( int i = h[x] ; ~i ; i = ne[i] )
  	{
  		int y = ver[i] ;
  		if( y == fa[x] || y== son[x] ) continue ;
  		dfs2( y , y ) ;
	}
}
int LCA( int u , int v )
{
	while( top[u] != top[v] )
	{
		if( dep[u] < dep[v] ) swap( u , v ) ;
		u = fa[top[u]] ;
	}
	return dep[u]>dep[v] ? v : u ;
}
int Distant( int u , int v )
{
	int z = LCA ( u , v ) ;
	return dis[u] + dis[v] - dis[z] * 2 ; 
}
struct Segment_Tree
{
	int l,r;
	int diameter_l,diameter_r;//直径两端点的编号 dfn连续 rnk查询点
	int d;
}tree[N*4]; 
Segment_Tree merge( Segment_Tree a , Segment_Tree b )
{ 
	Segment_Tree new_tree ;
	int l1 = a.diameter_l , r1 = a.diameter_r ;
	int l2 = b.diameter_l , r2 = b.diameter_r ;
	int L = a.l , R = b.r ;
	int x1 = Distant ( l1 , l2 ) , x2 = Distant ( l1 , r2 ) , x3 = Distant ( r1 , l2 ) , x4 = Distant ( r1 , r2 ) ;
	if ( x1 >= x2 && x1 >= x3 && x1 >= x4 )
	{
		new_tree.diameter_l = l1 ;
		new_tree.diameter_r = l2 ;
		new_tree.d = x1 ;
	}
	else if ( x2 >= x1 && x2 >= x3 && x2 >= x4 )
	{
		new_tree.diameter_l = l1 ;
		new_tree.diameter_r = r2 ;
		new_tree.d = x2 ;
	}
	else if ( x3 >= x1 && x3 >= x2 && x3 >= x4 )
	{
		new_tree.diameter_l = r1 ;
		new_tree.diameter_r = l2 ;
		new_tree.d = x3 ;
	}
	else 
	{
		new_tree.diameter_l = r1 ;
		new_tree.diameter_r = r2 ;
		new_tree.d = x4 ;
	}
	if ( a.d > new_tree.d ) 
	{
		new_tree.diameter_l = l1 ;
		new_tree.diameter_r = r1 ;
		new_tree.d = a.d ;
	}
	if ( b.d > new_tree.d ) 
	{
		new_tree.diameter_l = l2 ;
		new_tree.diameter_r = r2 ;
		new_tree.d = b.d ;
	}
	new_tree.l = L ; new_tree.r = R ;
	return new_tree;
} 
void update(int pos) // merge 点集 
{
	tree[pos] = merge ( tree[ls] , tree[rs] ) ; 
	tree[pos].l = tree[ls].l ; tree[pos].r = tree[rs].r ; 
}
void build(int pos,int l,int r)
{ 
	tree[pos].l = l ; tree[pos].r = r ; 
	if( l == r ) { tree[pos].diameter_l = l ; tree[pos].diameter_r = l ; return ; }
	int mid = l + r >> 1 ;
	build( ls , l , mid ) ;
	build( rs , mid + 1 , r ) ;
	update( pos ) ;
}
Segment_Tree query( int pos , int l , int r ) // 返回结构体 因为合并需要子节点信息 
{  
	if( l <= tree[pos].l && tree[pos].r <= r ) return tree[pos] ;  
	int mid = tree[pos].l + tree[pos].r >> 1 ; 
	if( mid < l ) return query( rs , l , r ) ; 
	if( mid + 1 > r  ) return query( ls , l , r ) ;
	return merge( query( ls , l , r ) , query( rs , l , r ) ) ;
}
signed main()
{
	memset( h , -1 , sizeof h ) ;
    scanf("%lld%lld",&n,&q); 
    for( int i = 1 ; i < n ; i++ )
    {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        link( u , v , w ) ; link( v , u , w ) ;
    }
    dfs1( 1 , 0 , 0 ) ; 
    dfs2( 1 , 1 ) ; 
    build( 1 , 1 , n ) ;    
    for( int i = 1 ; i <= q ; i++ ) 
    { 
    	int l1,r1,l2,r2;
    	scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2) ;
    	int ans = 0 ;
    	Segment_Tree x = query( 1 , l1 , r1 ) , y = query( 1 , l2 , r2 ) ; 
    	int u , v , w ;
    	u = x.diameter_l , v = y.diameter_l ; w = Distant( u , v ) ; if( w > ans ) ans = w ; 
    	u = x.diameter_l , v = y.diameter_r ; w = Distant( u , v ) ; if( w > ans ) ans = w ; 
    	u = x.diameter_r , v = y.diameter_l ; w = Distant( u , v ) ; if( w > ans ) ans = w ; 
    	u = x.diameter_r , v = y.diameter_r ; w = Distant( u , v ) ; if( w > ans ) ans = w ; 
    	printf("%lld\n",ans) ; 
	}
}