传送门：

题目大意

给一棵n个点的无根树，每条树边i给出li和ri表示速度在[li，ri]内才能通过这条边。

现在有m个询问，每个询问给出一个速度x，求以x的速度（不能改变）能在树上通过的路径长度的最大值（起点和终点任意）。

n,m<=70000;1<=li,ri<=n;

来源&写因

这题是在dalao们成外集训最后一场考试的T3，听说当时无人AC，确实挺难的，我自问也只会写n^2暴力。

正解充分运用了线段树的性质，前些天新学的线段树优化建图也有异曲同工之妙，感觉领悟到了线段树的一些精髓，所以来写篇题解。

题解

m跟n同级，也就是说得求出速度为1~n时的答案，再O（1）回答询问。

对于一个速度x，如果我们只在树上留下速度区间包含x的边，删去其它边，会得到一个森林，答案就是其中最长直径。那么我们肯定要考虑动态维护一个森林的最长直径，也就是说，维护其中每一个连通块的最长链，支持加边操作。并查集加树的直径的性质可以轻松实现。

问题是哪些区间包含x呢？

设n=8，x=3

发现包含x的区间即为包含[3]或[3,4]或[1,4]的所有区间。

这启发我们用线段树做。

首先对于线段树上的每一个节点node，存下所有包含了node所代表区间的边（直接用链表存）。

然后求答案时遍历一遍线段树，每走到一个节点node，就施加node的链表里存的边的影响，而每离开一个节点node，就撤销node的链表里存的边的影响。这样子当遍历到线段树的一个叶子节点时，设l=r=x，我们恰好施加了所有包含x的边的影响，答案就有了。

注意到我们需要撤销影响，可持久化并查集，其实用个栈存操作信息，回溯时怎么改的就怎么改回去就好了，可以发现进栈元素个数是nlogn的。但是这样做的话并查集就绝不能路径压缩了，于是复杂度就变得相当玄学，然而实测即使是在链的情况也跑得飞起==

自然语言太无力了，还是看代码吧。

#include
    
     using namespace std;const int N=70005,M=N*20;inline int read(){    int x=0,w=0;char ch=0;    while(!isdigit(ch)) w|=ch=='-',ch=getchar();    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    return w?-x:x; }vector
     
       to[N];namespace sp{    int dep[N],fa[N],sz[N],son[N],top[N];    void dfs1(int x,int pre){        dep[x]=dep[pre]+1;fa[x]=pre;sz[x]=1;        for(int i=0;i
      
       sz[son[x]]) son[x]=y;        }     }       void dfs2(int x,int pre){        top[x]=pre;        if(son[x]) dfs2(son[x],pre);        for(int i=0;i
       
        res) nl=l[x],nr=r[x],res=f[x];        if(f[y]>res) nl=l[y],nr=r[y],res=f[y];        t=dist(l[x],l[y]);        if(t>res) nl=l[x],nr=l[y],res=t;        t=dist(r[x],r[y]);        if(t>res) nl=r[x],nr=r[y],res=t;        t=dist(l[x],r[y]);        if(t>res) nl=l[x],nr=r[y],res=t;        t=dist(r[x],l[y]);        if(t>res) nl=r[x],nr=l[y],res=t;        q[++cur]=(opt){0,y,0};        q[++cur]=(opt){1,x,l[x]};        q[++cur]=(opt){2,x,r[x]};        q[++cur]=(opt){3,x,f[x]};        fa[y]=x,l[x]=nl,r[x]=nr,f[x]=res;        ans=max(ans,res);     }    void retrace(int tim){        while(cur>tim){            switch(q[cur].id){                case 0:fa[q[cur].x]=q[cur].x;break;                case 1:l[q[cur].x]=q[cur].val;break;                case 2:r[q[cur].x]=q[cur].val;break;                case 3:f[q[cur].x]=q[cur].val;break;            }             --cur;        }    }}namespace sg{    int tot,tail[N<<2];    struct edge{        int u,v,last;    }e[M];    #define tl id<<1    #define tr id<<1|1    #define mid (l+r>>1)    #define lson tl,l,mid    #define rson tr,mid+1,r     void update(int id,int l,int r,int ll,int rr,int u,int v){        if(ll<=l&&r<=rr){            e[++tot]=(edge){u,v,tail[id]};            tail[id]=tot;            return ;        }        if(rr<=mid) update(lson,ll,rr,u,v);        else if(ll>mid) update(rson,ll,rr,u,v);        else update(lson,ll,rr,u,v),update(rson,ll,rr,u,v);    }    int ans[N];    void solve(int id,int l,int r,int res){        int tim=cur;        for(int p=tail[id];p;p=e[p].last) st::merge(e[p].u,e[p].v,res);        if(l==r){            ans[l]=res;            st::retrace(tim);            return ;        }        solve(lson,res),solve(rson,res);        st::retrace(tim);    }}int main(){    n=read(),m=read();    for(int i=1,u,v,l,r;i
       
      
     
    

---

1. 设树A和树B，树A直径的端点为la和ra，树B直径的端点为lb和rb。在A和B之间连一条边后，得到的新树的直径的端点一定是la，ra，lb，rb中的两个。