车速

车速

关注
发信
关注(28)粉丝(399)

Dash Speed【好题，分治，并查集按秩合并】

Dash Speed

题目描述

比特山是比特镇的飙车圣地。在比特山上一共有 n 个广场，编号依次为 1 到 n，这些广场之间通过 n − 1 条双向车道直接或间接地连接在一起，形成了一棵树的结构。

因为每条车道的修建时间以及建筑材料都不尽相同，所以可以用两个数字 li, ri 量化地表示一条车道 的承受区间，只有当汽车以不小于 li 且不大于 ri 的速度经过这条车道时，才不会对路面造成伤害。

Byteasar 最近新买了一辆跑车，他想在比特山飙一次车。Byteasar 计划选择两个不同的点 S, T ，然 后在它们树上的最短路径上行驶，且不对上面任意一条车道造成伤害。

Byteasar 不喜欢改变速度，所以他会告诉你他的车速。为了挑选出最合适的车速，Byteasar 一共会 向你询问 m 次。请帮助他找到一条合法的道路，使得路径上经过的车道数尽可能多。

输入

第一行包含两个正整数 n, m，表示广场的总数和询问的总数。

接下来 n − 1 行，每行四个正整数 ui, vi, li, ri，表示一条连接 ui 和 vi 的双向车道，且承受区间为[li, ri]。

接下来 m 行，每行一个正整数 qi，分别表示每个询问的车速。

输出

输出 m 行，每行一个整数，其中第 i 行输出车速为 qi 时的最长路径的长度，如果找不到合法的路 径则输出 0。

样例

Input#1

5 3
3 2 2 4
1 5 2 5
4 5 2 2
1 2 3 5
1
2
3

Output#1

0
2
3

样例解释：
当车速为 1 时，不存在合法的路径。
当车速为 2 时，可以选择 1-5-4 这条路径，长度为 2。
当车速为 3 时，可以选择 3-2-1-5 这条路径，长度为 3

题解

Substack1：暴力

对于每个询问直接枚举一个端点，然后dfs一遍，找最大距离。

时间复杂度为\(O(M\cdot N^2)\)，期望得分20。

Substack2：树退化成链且l=1

由于l没有限制了，只要当前边的r大于等于限制lim，则可以通过。考虑离线询问，以r为关键字排序所有连边及询问，用并查集维护连通块，每个连通块记录两个值\(ma，mi\)，表示该连通块内节点的最大/最小深度，则当前连通块构成的链长度为\(ma-mi\)。

时间复杂度为\(O(NlogN+M)\)，结合Substack1期望得分40。

Substack3：树退化成链的所有情况

比起Substack2，这里还要考虑l的限制。

枚举当前车速，则假如一条边限制车速为{\(l,r\)}，则在车速为\(l\)时加入这条连边，在车速为\(r+1\)时删除这条连边，对于每个车速，答案为当前所有连边形成的最大链长。

维护可以利用线段树。具体维护内容如下，对于线段树上的每个节点，设其对应树边范围为\((l,r)\)，维护三个值\((li,ri,S)\)，\(li\)表示\(l\)向右能延伸的最大连续长度，\(ri\)表示\(r\)向左能延伸的最大连续长度，\(S\)表示改区间内的最大链长。

时间复杂度为\(O(NlogN+M)\)，结合Substack1期望得分60。

前面三种情况的切分代码如下：

#include<bits/stdc++.h>
using namespace std;
#define R register

bool nc1;
const int N=70010;
inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
struct edge{
    int to,nxt,l,r;
}e[N<<1];
int ecnt,head[N];
inline void link(int u,int v,int l,int r){
    e[++ecnt]=(edge){v,head[u],l,r};
    head[u]=ecnt;
}
int n,m;
namespace SUB1_bl{//o(M*(N^2)):n,m<=20
    int now=0,lim;
    void dfs(int x,int f,int dis){
        if(dis>now)now=dis;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to,l=e[i].l,r=e[i].r;
            if(y==f||lim<l||lim>r)continue;
            dfs(y,x,dis+1);
        }
    }
    void solve(){
        while(m--){
            lim=read();now=0;
            for(R int i=1;i<=n;++i)dfs(i,0,0);
            printf("%d\n",now);
        }
    }
}
struct EE{
    int x,d;
}E[N];
vector<int>que[N];
int res[N];
inline bool cmpsub2(EE a,EE b){return a.d<b.d;}
namespace SUB2_linkandL{//O(NlogN+M) 所有l=1且形态为链
    int ma[N],mi[N],CNT,tmp[N],bcj[N],ans=0;
    int find(int k){return bcj[k]==k?k:bcj[k]=find(bcj[k]);}
    void solve(){
        for(R int x=1;x<=n;x++){
            ma[x]=mi[x]=bcj[x]=x;
            for(R int i=head[x];i;i=e[i].nxt){
                int y=e[i].to;
                if(y==x+1){
                    E[++CNT]=(EE){x,e[i].r};
                    tmp[CNT]=e[i].r;
                    break;
                }
            }
        }
        sort(E+1,E+CNT+1,cmpsub2);
        sort(tmp+1,tmp+CNT+1);

        for(R int i=1;i<=m;++i){
            int qnum=read();
            qnum=lower_bound(tmp+1,tmp+CNT+1,qnum)-tmp;
            que[qnum].push_back(i);
        }

        for(R int i=CNT;i>=1;i--){
            int u=E[i].x,v=u+1,A=find(u),B=find(v);
            if(A==B)continue;
            bcj[A]=B;
            ma[B]=max(ma[B],ma[A]);
            mi[B]=min(mi[B],mi[A]);
            ans=max(ans,ma[B]-mi[B]);
            for(int j=0;j<que[i].size();++j)res[que[i][j]]=ans;
        }
        for(R int i=1;i<=m;++i)printf("%d\n",res[i]);

    }
}
typedef pair<int,int> pii;
vector<pii>g[N];
namespace SUB3_LINK{//链的所有情况
    struct SGT{
        int l,r;
        int S,li,ri;
        /*S:区间内最大连续链长
          li:左端点向右的最大连续距离
          ri:右端点向左的最大连续距离
        */
    }b[N<<2];
    void build(int o,int l,int r){
        b[o].l=l,b[o].r=r,b[o].S=b[o].li=b[o].ri=0;
        if(l==r)return;
        int mid=l+r>>1;
        build(o<<1,l,mid),build(o<<1|1,mid+1,r);
    }
    void up(int o){
        int ls=o<<1,rs=o<<1|1;
        int sizL=b[ls].r-b[ls].l+1,sizR=b[rs].r-b[rs].l+1;
        b[o].S=max(max(b[ls].S,b[rs].S),b[ls].ri+b[rs].li);
        b[o].li=b[ls].li;
        if(b[ls].li==sizL)b[o].li+=b[rs].li;
        b[o].ri=b[rs].ri;
        if(b[rs].ri==sizR)b[o].ri+=b[ls].ri;
    }
    void update(int o,int pos,int z){
        if(b[o].l==b[o].r){
            b[o].S=b[o].li=b[o].ri=z;
            return;
        }
        int mid=b[o].l+b[o].r>>1;
        if(pos<=mid)update(o<<1,pos,z);
        else update(o<<1|1,pos,z);
        up(o);
    }
    void solve(){
        for(R int x=1;x<n;x++){
            for(R int i=head[x];i;i=e[i].nxt){
                int y=e[i].to;
                if(y==x+1){
                    g[e[i].l].push_back(make_pair(x,1));
                    g[e[i].r+1].push_back(make_pair(x,0));
                    break;
                }
            }
        }
        for(R int i=1;i<=m;i++){
            int x=read();
            que[x].push_back(i);
        }
        build(1,1,n-1);//n-1条线段
        for(R int i=1;i<=n;i++){
            for(R int j=0;j<g[i].size();j++)update(1,g[i][j].first,g[i][j].second);
            for(R int j=0;j<que[i].size();j++)res[que[i][j]]=b[1].S;
        }
        for(R int i=1;i<=m;i++)printf("%d\n",res[i]);
    }
}
bool nc2;
int main(){
    //cout<<(&nc2-&nc1)/1024/1024<<endl;
//  freopen("speed.in","r",stdin);
//  freopen("speed.out","w",stdout);
    n=read(),m=read();
    bool islink=1,Lequal1=1;
    for(int i=1;i<n;++i){
        int u=read(),v=read(),l=read(),r=read();
        link(u,v,l,r);link(v,u,l,r);
        if(u!=v+1&&v!=u+1)islink=0;
        if(l!=1)Lequal1=0;
    }
    if(n<=20){SUB1_bl::solve();return 0;}
    if(islink&&Lequal1){SUB2_linkandL::solve();return 0;}
    if(islink){SUB3_LINK::solve();return 0;}
}

Substack4：l=1的所有情况

只用考虑r的限制。

之前NOIP真题有做过类似的，好像是这题NOIP2013 货车运输。货车运输这题是给你每条路的承重量，多个询问，问你从u到v最多能带多少货物。做法是离线询问，从限制最宽(承重量最大)的边开始加，然后对于新生成的树启发式合并，维护两点连通情况，顺便更新答案。

两点连通情况不难维护，但本题需要维护的是新树的直径。

仍然基于Substack2的想法，但是现在新树直径不是链长了。对于当前边\((x,y)\)，如果已经同属于一棵树了就continue掉，反之对于分别属于的两棵树进行合并，并对新合并的树求直径。

每个连通块(树)，维护两个东西{\(A[],B[]\)}，分别表示该连通块(树)的直径的两个端点。

对于合并后的新树，不难知道，新直径只可能有\(C_4^2=6\)种情况，即在原来的四个端点中选两个作为新树的端点，比较形成的直径长度，取6种中最长的一个更新。如何快速求两点距离呢？其实它就等于原树（所有边都连上时）上的距离，那么用树剖/倍增直接求LCA然后求原树上的距离即可。

时间复杂度为\(O(NlogN+M)\)，结合Substack1,Substack3期望得分80。

Substack5：所有情况

现在还要考虑上l的限制了：（

由于车速处在\([1,n]\)间，考虑预处理完所有\(ans[i=1..n]\)表示车速为i时能走的最长路径，然后直接在线回答询问。

考虑根据车速来分治。对于当前区间\([l,r]\)，设道路限速为\([ql,qr]\)。则将所有满足\(ql<=l,r<=qr\)的道路存在这个速度区间里（表示这个道路限度完全包含这个速度区间）。像下面这样：

//当前存的道路限速为[ql,qr]，当前车速区间为[l,r]，节点编号为o
//u,v是道路的两个端点
int head[N<<2],U[N*20],V[N*20],nxt[N*20],ecnt;
//大概N<<2个节点，大概会存N*logN次边
void Insert(int o,int l,int r,int ql,int qr,int u,int v){
    if(ql<=l&&r<=qr){
        U[++ecnt]=u;V[ecnt]=v;
        nxt[ecnt]=head[o];head[o]=ecnt;//前向星存边
        return;
    }
    int mid=l+r>>1;
    if(ql<=mid)Insert(o<<1,l,mid,ql,qr,u,v);
    if(qr>mid)Insert(o<<1|1,mid+1,r,ql,qr,u,v);
}

先来分析一下单单这样存边的复杂度，m条边每条边都存一次，递归层数为\(logN\)，所以\(O(MlogN)\)。顺便注意一下存边数组的大小。

存完边后开始分治连边。

//当前节点为o，速度区间为[l,r]，ret表示此时的树上最大链长
void solve(int o,int l,int r,int ret){
    int pos=cur;//cur和pos的具体用处下面会讲到
    for(R int i=head[o];i;i=nxt[i])merge(U[i],V[i],ret);
    //merge(u,v,ret)表示连接uv这条边，并更新当前ret
    if(l==r){
        ans[l]=ret;//当递归到叶子时得到ans
        Retrace(pos);//Retrace:回溯
        return;
    }
    int mid=l+r>>1;
    solve(o<<1,l,mid,ret);
    solve(o<<1|1,mid+1,r,ret);
    Retrace(pos);//分治到另一半时还得把当前这一半的影响给回溯了
}

merge函数的具体实现跟Substack4里讲的基本一样，利用并查集维护连通关系（但不能路径压缩，因为之后还要回溯）和当前树内的两个直径端点A[i],B[i],然后直接枚举\(C_4^2=6\)种情况，去更新新树的直径大小及端点。

代码如下：

int Find(int x){return fa[x]==x?x:Find(fa[x]);}
inline void Dia(int a,int b,int &P1,int &P2,int &ma){//考虑(a,b)作为新树直径的情况
    int tmp=dep[a]+dep[b]-2*dep[LCA(a,b)];//这个LCA在前面预处理出来，倍增或树剖
    if(tmp>ma)ma=tmp,P1=a,P2=b;//更新直径长度及两个端点
}
inline void merge(int x,int y,int &ret){//在(x,y)间连边，形成新树
    x=Find(x),y=Find(y);
    int P1,P2,ma=-1,tmp;
    //六种情况
    Dia(A[x],B[x],P1,P2,ma);
    Dia(A[x],A[y],P1,P2,ma);
    Dia(A[x],B[y],P1,P2,ma);
    Dia(B[x],A[y],P1,P2,ma);
    Dia(B[x],B[y],P1,P2,ma);
    Dia(A[y],B[y],P1,P2,ma);
    if(ma>ret)ret=ma;
    //!!!!
    if(rk[x]==rk[y]){//当两树秩相等时，将Treey连到Treex上，Treex的秩++
        rk[x]++;
        op[++cur]=(Op){0,x,0};
    }
    if(rk[x]<rk[y])swap(x,y);

    op[++cur]=(Op){1,y,0};
    op[++cur]=(Op){2,x,A[x]};
    op[++cur]=(Op){3,x,B[x]};
    fa[y]=x,A[x]=P1,B[x]=P2;
    //!!!!
}

看到下面重点标记的部分，这一部分其实就是按秩合并两棵树，并且为之后的回溯操作做准备。

按秩合并的部分不难理解，就是将高度(秩)较小的树连在高度(秩)较大的树上。为回溯做准备的代码可以结合下面回溯代码去理解。

op这个结构体记录回溯操作，用类似栈的形式去存储回溯操作，cur就表示当前栈内元素(需要回溯的操作)。现在就可以解释之前分治函数solve()中这句代码的意义了int pos=cur;//cur和pos的具体用处下面会讲到，它存储了递归子树前栈顶的位置，现在我去分治另一半时只用回到pos位置即可。

struct Op{//记录回溯操作
    int t,x,y;
}op[N<<2];
inline void Retrace(int pos){//回溯到pos位置
    while(cur>pos){
        if(op[cur].t==0)rk[op[cur].x]--;
        if(op[cur].t==1)fa[op[cur].x]=op[cur].x;
        if(op[cur].t==2)A[op[cur].x]=op[cur].y;//还原该树直径端点1
        if(op[cur].t==3)B[op[cur].x]=op[cur].y;//还原该树直径端点2
        cur--;
    }
}

这样整个做法就结束了，具体实现时注意细节，包括数组大小/数组名混淆/不能路径压缩这些。

上面的分治做法看似非常暴力，来分析一下复杂度，边存储了\(MlogN\)次，每条边都至多merge()和出栈一次，考虑上并查集的查找，整个算法的时间复杂度大致为\(O(Nlog^2N)\)。

完整代码如下：

#include<bits/stdc++.h>
#define R register
using namespace std;
const int N=70010;
int n,m,cur,ans[N];
int sz[N],f[N],dep[N],son[N],top[N];//树剖
int fa[N],rk[N],A[N],B[N];//并查集

int head[N<<2],U[N*20],V[N*20],nxt[N*20],ecnt;
inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
struct Op{//记录回溯操作
    int t,x,y;
}op[N<<2];
vector<int>g[N];
void dfs(int x){
    sz[x]=1;
    for(int i=0;i<g[x].size();++i){
        int y=g[x][i];if(y==f[x])continue;
        f[y]=x,dep[y]=dep[x]+1;
        dfs(y),sz[x]+=sz[y];
        if(sz[y]>sz[son[x]])son[x]=y;
    }
}
void redfs(int x,int tp){
    top[x]=tp;
    if(son[x])redfs(son[x],tp);
    for(int i=0;i<g[x].size();++i){
        int y=g[x][i];if(y==f[x]||y==son[x])continue;
        redfs(y,y);
    }
}
inline int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=f[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int Find(int x){return fa[x]==x?x:Find(fa[x]);}
inline void Dia(int a,int b,int &P1,int &P2,int &ma){//考虑(a-b)作为新树直径的情况
    int tmp=dep[a]+dep[b]-2*dep[LCA(a,b)];
    if(tmp>ma)ma=tmp,P1=a,P2=b;
}
inline void merge(int x,int y,int &ret){//在(x,y)间连边，形成新树
    x=Find(x),y=Find(y);
    int P1,P2,ma=-1,tmp;
    Dia(A[x],B[x],P1,P2,ma);
    Dia(A[x],A[y],P1,P2,ma);
    Dia(A[x],B[y],P1,P2,ma);
    Dia(B[x],A[y],P1,P2,ma);
    Dia(B[x],B[y],P1,P2,ma);
    Dia(A[y],B[y],P1,P2,ma);
    if(ma>ret)ret=ma;

    if(rk[x]==rk[y]){//当两树秩相等时，将Treey连到Treex上，Treex的秩++
        rk[x]++;
        op[++cur]=(Op){0,x,0};
    }
    if(rk[x]<rk[y])swap(x,y);
    op[++cur]=(Op){1,y,0};
    op[++cur]=(Op){2,x,A[x]};
    op[++cur]=(Op){3,x,B[x]};
    fa[y]=x,A[x]=P1,B[x]=P2;
}
inline void Retrace(int pos){//回溯
    while(cur>pos){
        if(op[cur].t==0)rk[op[cur].x]--;
        if(op[cur].t==1)fa[op[cur].x]=op[cur].x;
        if(op[cur].t==2)A[op[cur].x]=op[cur].y;//还原该树直径端点1
        if(op[cur].t==3)B[op[cur].x]=op[cur].y;//还原该树直径端点2
        cur--;
    }
}
void Insert(int o,int l,int r,int ql,int qr,int u,int v){
    if(ql<=l&&r<=qr){
        U[++ecnt]=u;V[ecnt]=v;
        nxt[ecnt]=head[o];head[o]=ecnt;//存边
        return;
    }
    int mid=l+r>>1;
    if(ql<=mid)Insert(o<<1,l,mid,ql,qr,u,v);
    if(qr>mid)Insert(o<<1|1,mid+1,r,ql,qr,u,v);
}
void solve(int o,int l,int r,int ret){
    int pos=cur;
    for(R int i=head[o];i;i=nxt[i])merge(U[i],V[i],ret);
    if(l==r){
        ans[l]=ret;
        Retrace(pos);
        return;
    }
    int mid=l+r>>1;
    solve(o<<1,l,mid,ret);
    solve(o<<1|1,mid+1,r,ret);
    Retrace(pos);
}
int main(){
    n=read(),m=read();
    for(R int i=1;i<n;++i){
        int u=read(),v=read(),l=read(),r=read();
        g[u].push_back(v);
        g[v].push_back(u);
        Insert(1,1,n,l,r,u,v);
    }
    dfs(1);redfs(1,1);
    for(R int i=1;i<=n;++i)fa[i]=A[i]=B[i]=i;
    solve(1,1,n,0);
    while(m--)printf("%d\n",ans[read()]);
}
01-26 00:01
Powered by LMLPHP ©2024 车速 0.070582