题目描述：

小 $H$ 是一位优秀的越野赛车女选手。现在她准备在 $A$ 山上进行赛车训练。

$A$ 山上一共有 $n$ 个广场，编号依次为 $1$ 到 $n$ ，这些广场之间通过 $n-1$条双向车道直接或间接地连接在一起。对于每条车道$i$ ，可以用四个正整数 $u_i,v_i,l_i,r_i$描述，表示车道连接广场 $u_i$ 和 $v_i$ ，其速度承受区间为$[l_i,r_i]$，即汽车必须以不小于$l_i$ 且不大于 $r_i$ 的速度经过车道$i$ 。

小 $H$ 计划进行 $m$ 次训练，每次她需要选择 $A$ 山上的一条简单路径，然后在这条路径上行驶。但小 $H$ 不喜欢改变速度，所以每次训练时的车速都是固定的。

现在小 $H$ 告诉你她在$m$ 次训练中计划使用的车速，请帮助她对于每次训练，找到一条合法的路径（车速在所有车道的速度承受区间的交集内），使得路径上经过的车道数最大。

算法标签：线段树，可持久化并查集，动态维护树的直径，rmq

思路：

建一棵以 $l,r$ 为下标的线段树，把每条边放到区间里，每次对于这个区间的边连到图中，启发式合并，并查集不路径压缩。用一个栈记录下每层实现了那些修改，把被修改的数记录下来，之后推出这层时复原。

对于直径的维护，每次使两个连通分量连接，可以证明直径一定是由未合并前两个联通块的直径的端点连接组成。考虑对于至多四个点枚举两两之间的路径长度，得到新联通块的直径。求 $lca$ 用 $rmq$ 提前预处理。

以下代码：

#include
      
       #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=7e4+5;int top,mx[N],Ans,tot;int d[N],id[N],rq[N<<1][20],sz[N],fa[N],p1[N],p2[N];int n,m,head[N],ne[N<<1],to[N<<1],cnt,Lg[N<<1],res[N],gg[4];vector
       
         t[N<<2],s[N];struct node{    int x,y;}g[N];struct data{    int x,y,len,p1,p2;}q[N];il int read(){   int x,f=1;char ch;   _(!)ch=='-'?f=-1:f;x=ch^48;   _()x=(x<<1)+(x<<3)+(ch^48);   return f*x;}il int Min(int x,int y){    return d[x]
        
         >1;    if(ql<=mid)ins(x<<1,l,mid,ql,qr,v);    if(mid
         
          <<1|1,mid+1,r,ql,qr,v);}il void dfs(int x,int fa){    id[x]=++tot;rq[tot][0]=x;    for(int i=head[x];i;i=ne[i]){        if(fa==to[i])continue;        d[to[i]]=d[x]+1;dfs(to[i],x);        rq[++tot][0]=x;    }}il int Lca(int x,int y){    int l=id[x],r=id[y];    if(l>r)swap(l,r);    int k=Lg[r-l+1];    return Min(rq[l][k],rq[r-(1<
          
           maxn)maxn=len,f1=gg[i],f2=gg[j];        }    }    p1[a]=f1;p2[a]=f2;mx[a]=maxn;fa[b]=a;sz[a]+=sz[b];    Ans=max(Ans,maxn);}il void del(int p){    while(top>p){        int a=q[top].x,b=q[top].y;        sz[a]-=sz[b];        fa[b]=b;mx[a]=q[top].len;        p1[a]=q[top].p1;p2[a]=q[top].p2;        top--;    }}il void solve(int x,int l,int r){    int tmp=top,ret=Ans;    for(int i=0;i
           
            >1; solve(x<<1,l,mid);solve(x<<1|1,mid+1,r); del(tmp);Ans=ret;}int main(){ n=read();m=read(); for(int i=1;i
            
             >1]+1; for(int j=1;j<=Lg[tot];j++)for(int i=1;i+(1<
             
              <=tot;i++) rq[i][j]=Min(rq[i][j-1],rq[i+(1<<(j-1))][j-1]); for(int i=1;i<=n;i++)sz[i]=1,fa[i]=p1[i]=p2[i]=i; solve(1,1,n); for(int i=1;i<=m;i++)printf("%d\n",res[i]); return 0;}