越野赛车问题
小 $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 140005using 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-(1dis(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