越野赛车问题
小 $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; }