牛客练习赛67 F.牛妹的苹果树

题目大意： 个点的无根树， 条带权边。有 次询问，每次询问区间 的点的.
表示 点到点的最短距离。

参考出题人题解：https://blog.nowcoder.net/n/13d05ab8ac22444a81fbe475de2f563e
HDU多校也出了一道这个题目求区间 .(怀疑出题人巨巨是同一个

分析；对于一个区间 的点集，求最大两点间的最短距离其实就是求点集的的直径。对于两个不同的点集 进行合并后， 点集的直径就是原先两个点集的直径两点，从该四点中点对距离产生。那么我们可以套个树链剖分LCA，线段树进行维护区间点集的直径合并操作，然后 进行回答询问。

#include<bits/stdc++.h>
using namespace std;

const int maxn=3e5+10;
const int mod=1e9+7;
typedef long long ll;

inline int read()
{
    int x=0;char s=getchar();
    for( ;isdigit(s);x=x*10+s-48,s=getchar());
    return x;
}

//*/ 建边 
struct Node{
    int to,next;
    ll w;
}edge[maxn<<2];

struct node{
    int x,y;
    ll w;
}tree[maxn<<2];

int tot,head[maxn];

void add( int u,int v ,ll w )
{
    edge[tot]={v,head[u],w};
    head[u]=tot++;
} 

void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}

int rk[maxn]; // [线段树编号] 对 应结点号 结点初始赋值数组 
//*/ 树链剖分 
int fa[maxn],dep[maxn],siz[maxn],top[maxn];
// 父亲 深度 大小 重链的头 
int v[maxn],son[maxn],dfn[maxn],w[maxn],tim;
//  [结点]权值 [结点]重儿子 时间戳(编号) 结点权值的[dfs序] 计数器 
ll dis[maxn];

void dfs1( int u,int f ) //找重链 
{
    fa[u]=f;    // 父节点 
    dep[u]=dep[f]+1; //当前深度 
    siz[u]=1;
    int maxsize=-1;
    for( int i=head[u];~i;i=edge[i].next )
    {
        int v=edge[i].to,w=edge[i].w;
        if( v==f ) continue;
        dis[v]=dis[u]+w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if( siz[v]>maxsize )
        {
            maxsize=siz[v];
            son[u]=v;
        }
    }
} 

void dfs2( int u,int t )
{
    dfn[u]=++tim;
    top[u]=t;
    w[tim]=v[u];
    rk[tim]=u;
    if( !son[u] ) return;
    dfs2(son[u],t);
    for( int i=head[u];~i;i=edge[i].next )
    {
        int v=edge[i].to;
        if( v==fa[u] || v==son[u] ) continue;
        dfs2(v,v);
    }
}

int lca( int x,int y )
{
    while( top[x]!=top[y] )
    {
        if( dep[top[x]]<dep[top[y]] ) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y] ? x : y;
} 

ll dist( int x,int y )
{
    return dis[x]+dis[y]-2*dis[lca(x,y)]; //
}



inline node Max( node a,node b )
{
    return dist(a.x,a.y)>dist(b.x,b.y) ? a : b;
} 

inline node push_up( node a,node b )
{
    node res=Max( Max( (node){a.x,b.x,0},(node){a.x,b.y,0} ),
                  Max( (node){a.y,b.x,0},(node){a.y,b.y,0} ) );
    res.w=dist( res.x,res.y );
    if( a.w>res.w ) res=a;
    if( b.w>res.w ) res=b;
    return res;
}

#define ls cur<<1
#define rs cur<<1|1
void build( int cur,int l,int r )
{
    if( l==r )
    {
        tree[cur]=(node){l,l,0};
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tree[cur]=push_up(tree[ls],tree[rs]);
}

inline node query( int cur,int l,int r,int L,int R )
{
    if( L<=l && r<=R ) return tree[cur];
    int mid=l+r>>1;
    bool ql=0,qr=0;
    node res1,res2;
    if( L<=mid ) ql=true,res1=query(ls,l,mid,L,R);
    if( R>mid ) qr=true,res2=query(rs,mid+1,r,L,R);
    return ( ql & qr ) ? push_up(res1,res2) : ( ql ? res1:res2 ); 
}

int main()
{
    int n,m;
    n=read(),m=read();
    init();
    for( int i=1;i<n;i++ )
    {
        int u,v,w;
        u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,w); 
    }
    int r=1; //树的根节点 

    dfs1(r,r);
    dfs2(r,r);
    build(1,1,n);

    while( m-- )
    {
        int x,y;x=read(),y=read();
        printf("%lld\n",query(1,1,n,x,y).w);
    }
}