越野赛车问题
小 $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$ 次训练中计划使用的车速，请帮助她对于每次训练，找到一条合法的路径(车速在所有车道的速度承受区间的交集内)，使得路径上经
过的车道数最大。
Sol
考虑线段树分治。按速度开线段树，把边加进去。
查询时用一个并查集维护当前树的直径。
画画图可以发现，合并完的两棵树的直径，一定是两棵树的直径各取一段拼在一起的来，或者是其中一棵树的直径。
那么我们再维护端点，也就可以维护答案了。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define maxn 140005
using namespace std;
int n,m,head[maxn],tot,st[maxn][21],deep[maxn],fi[maxn],sc;
int ans,qans[maxn],f[maxn],sz[maxn];
struct haha{vector<int>u,v;
}tr[maxn*4];
struct node{int v,nex;}e[maxn];
struct Node{int x,y;}c[maxn];
struct nod{int v,id,idf;int num,ans;Node df;
}q[maxn];
vector<nod>s;
bool cmp(nod a,nod b){return a.v<b.v;}
void add(int k,int l,int r,int li,int ri,int u,int v){if(l>=li&&r<=ri){tr[k].u.push_back(u);tr[k].v.push_back(v);return;}int mid=l+r>>1;if(li<=mid)add(k*2,l,mid,li,ri,u,v);if(ri>mid)add(k*2+1,mid+1,r,li,ri,u,v);
}
void lj(int t1,int t2){e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;
}
void dfs(int k,int fa){fi[k]=++sc;deep[k]=deep[fa]+1;st[sc][0]=deep[k];for(int i=head[k];i;i=e[i].nex){if(e[i].v==fa)continue;dfs(e[i].v,k);st[++sc][0]=deep[k];}
}
int getf(int k){return f[k]==k?k:getf(f[k]);}
int dis(int x,int y){int l=fi[x],r=fi[y];if(l>r)swap(l,r);int t=log2(r-l+1);int d=min(st[l][t],st[r-(1<<t)+1][t]);return deep[x]+deep[y]-2*d;
}
void hb(int k){int siz=tr[k].u.size();for(int i=0;i<siz;i++){int u=tr[k].u[i],v=tr[k].v[i];int fu=getf(u),fv=getf(v);if(sz[fu]<sz[fv])swap(fu,fv),swap(u,v);nod t;t.id=fv;t.idf=fu;t.v=sz[fv];t.df=c[fu];t.num=k;s.push_back(t);sz[fu]+=sz[fv];f[fv]=fu;int x1=dis(c[fu].x,u)>dis(c[fu].y,u)?c[fu].x:c[fu].y;int x2=dis(c[fv].x,v)>dis(c[fv].y,v)?c[fv].x:c[fv].y;if(dis(x1,x2)>dis(c[fu].x,c[fu].y))c[fu]=(Node){x1,x2};if(dis(c[fv].x,c[fv].y)>dis(c[fu].x,c[fu].y))c[fu]=c[fv];ans=max(ans,dis(c[fu].x,c[fu].y));}
}
void turn(int k){int siz=s.size();for(int i=siz-1;i>=0;i--){if(s[i].num!=k)break;int fu=s[i].idf,fv=s[i].id;f[fv]=fv;sz[fu]-=s[i].v;c[fu]=s[i].df;s.pop_back();}
}
void solve(int k,int l,int r,int ql,int qr){if(ql>qr)return;int la=ans;hb(k);if(l==r){for(int i=ql;i<=qr;i++)qans[q[i].id]=ans;ans=la;turn(k);return;}int mid=l+r>>1;int sp;for(sp=ql-1;q[sp+1].v<=mid&&sp<qr;sp++);solve(k*2,l,mid,ql,sp);solve(k*2+1,mid+1,r,sp+1,qr);ans=la;turn(k);
}
int main(){cin>>n>>m;for(int i=1,u,v,t1,t2;i<n;i++){scanf("%d%d%d%d",&u,&v,&t1,&t2);add(1,1,n,t1,t2,u,v);lj(u,v);lj(v,u);}dfs(1,0);for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)<=sc+1;i++)st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);for(int i=1;i<=m;i++){scanf("%d",&q[i].v);q[i].id=i;}sort(q+1,q+m+1,cmp);for(int i=1;i<=n;i++)f[i]=i,c[i].x=c[i].y=i;solve(1,1,n,1,m);for(int i=1;i<=m;i++)cout<<qans[i]<<endl;return 0;
}
