越野赛车问题
小 $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
#include
#include
#include
#include
#include
#include
#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{vectoru,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];
vectors;
bool cmp(nod a,nod b){return a.v=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<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>n>>m;for(int i=1,u,v,t1,t2;i
View Code
