题解：P13542 [OOI 2022] Two avenues

· · 题解

难写的单 \log 做法。

考虑一条边怎样产生贡献：

最优的两条大道只有两种可能：

第一类是好做的，边双缩点后得到树，可以树上差分求每条边经过次数。

对于第二类，在每个边双内部做边三连通分量缩点，每个边三缩成一个圆点，每个环缩成一个方点，形成一棵圆方树。一个方点 x 对应一个环，一个询问经过方点 x，在环上产生一个区间。选两条环边切两刀，环被分成两段。一个区间被“切开”当且仅当两条切边恰有一条落在该区间对应的弧上。被切开的区间，其对应询问必须至少经过一条收费边。

对于一个方点 x，问题变成：环上有若干带权区间。选两条不同的环边切两刀，最大化被切开的区间权值和。

想一下怎么算切开区间权值和的最大值。考虑扫描线，枚举第一刀，然后可以线段树维护第二刀落在所有位置的贡献，当一刀进入某个区间时，给这个区间减去贡献，它的补集加上贡献，离开区间同理。注意环上的区间要拆开处理。

我们还要把所有环上的区间弄出来，肯定不能直接遍历。还是树上差分，一个路径 (a,b)，设 l=\operatorname{lca}(a,b)，则在 a\to l,b\to l 上，方点区间都形如从某个儿子 c 进入，再从父亲 fa 离开，维护 u 向父亲走的路径数，再单独处理转折处形成的一个额外区间，总区间数就是 O(n) 的了。

最后时间复杂度 O(n\log n)，可以感受到代码很难写（虽然有很多部分可以复制板子）。 ::::info[code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937_64 gen(time(NULL));
uniform_int_distribution<uint64_t>dist(0,(1ULL<<63)-1);
ll Rnd(){return dist(gen);}

const int N=5e5+10,inf=1e9;
int Gr,g,n,m,K,cnt;
int ex[N],ey[N],a[N],b[N];
vector<pair<int,int> >v[N];
void link(int x,int y){
    cnt++;
    v[x].push_back({y,cnt});
    v[y].push_back({x,cnt});
}
namespace part1{//割边切两刀 
    int dfu,top,cnt;
    int stk[N],dfn[N],low[N],cut0[N*2],col[N];
    void tarjan(int u,int fr){
        dfn[u]=low[u]=++dfu,stk[++top]=u;
        for(auto [to,id]:v[u]){
            if(id==fr) continue;
            if(!dfn[to]){
                tarjan(to,id);
                low[u]=min(low[u],low[to]);
                if(low[to]>=dfn[to]) cut0[id]=1;
            }
            else low[u]=min(low[u],dfn[to]);
        }
        if(low[u]==dfn[u]){
            cnt++;
            while(stk[top]!=u) col[stk[top--]]=cnt;
            col[stk[top--]]=cnt;
        }
    }
    vector<int>tr[N];
    void linkt(int x,int y){
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    struct qry{
        int df,f[21][N],dfn[N],dep[N];
        void dfs(int u,int fa){
            f[0][dfn[u]=++df]=fa;
            for(int t:tr[u])
              if(t!=fa)
                dep[t]=dep[u]+1,dfs(t,u);
        }
        int get(int x,int y){
            return dfn[x]<dfn[y]?x:y;
        }
        void init(int n){
            for(int i=1;i<=19;i++)
              for(int j=1;j+(1<<i)-1<=n;j++)
                f[i][j]=get(f[i-1][j],f[i-1][j+(1<<i-1)]);
        }
        int lca(int x,int y){
            if(x==y) return x;
            if((x=dfn[x])>(y=dfn[y])) swap(x,y);
            x++;int d=log2(y-x+1);
            return get(f[d][x],f[d][y-(1<<d)+1]);
        }
    }T;
    int val[N];
    void buildtree(){
        for(int i=1;i<=m;i++)
            if(col[ex[i]]!=col[ey[i]]) linkt(col[ex[i]],col[ey[i]]);
        T.dfs(1,0),T.init(cnt);
    }
    void dfs(int u,int fa){
        for(int to:tr[u]){
            if(to==fa) continue;
            dfs(to,u),val[u]+=val[to];
        }
    }
    vector<int>solve(){
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i,0);
        buildtree();
        for(int i=1;i<=K;i++){
            int x=col[a[i]],y=col[b[i]];
            val[x]++,val[y]++,val[T.lca(x,y)]-=2;
        }
        dfs(1,0);
        int mx1=0,mx2=0,a=0,b=0,c=0,d=0;
        for(int i=2;i<=cnt;i++){
            if(val[i]>mx1) mx2=mx1,c=a,d=b,mx1=val[i],a=i,b=T.f[0][T.dfn[i]];
            else if(val[i]>mx2) mx2=val[i],c=i,d=T.f[0][T.dfn[i]];
        }
        for(int i=1;i<=m;i++){
            int x=col[ex[i]],y=col[ey[i]];
            if((x==a&&y==b)||(x==b&&y==a)){a=ex[i],b=ey[i];break;}
        }
        for(int i=1;i<=m;i++){
            int x=col[ex[i]],y=col[ey[i]];
            if((x==c&&y==d)||(x==d&&y==c)){c=ex[i],d=ey[i];break;}
        }
        return {mx1+mx2,a,b,c,d};
    }
    void Clear(){
        for(int i=1;i<=cnt;i++) tr[i].clear();
        for(int i=1;i<=n;i++) dfn[i]=low[i]=stk[i]=cut0[i]=col[i]=val[i]=0;
        for(int i=1;i<=cnt;i++) T.dfn[i]=T.dep[i]=0;
        for(int i=1;i<=m;i++) cut0[i]=0;
        T.df=dfu=top=cnt=0;
    }
};
namespace part2{//边双非边三切某个环
    ll w[N*2];
    int dfu,Cnt;
    int dfn[N],ist[N*2],cut0[N*2],cut[N*2],fa[N],col[N];
    map<ll,int>mp1,mp2;
    void dfs3(int u,int t,int fr,int idx){//collect
        col[u]=idx;
        for(auto [to,id]:v[u]){
            if(id==fr||cut0[id]||cut[id]||!ist[id]) continue;
            if(to==t){ist[id]=0;continue;}
            dfs3(to,t,id,idx);
        }
    }
    void dfs2(int u,int fr){
        int siz=v[u].size();
        for(int i=0;i<siz;i++){
            int to=v[u][i].first,id=v[u][i].second;
            if(id==fr||cut0[id]||cut[id]||!ist[id]) continue;
                dfs2(to,id);
        }   
        if(mp2.count(w[u])){
            int to=mp2[w[u]];
            ist[fr]=0;
            Cnt++,dfs3(u,to,0,Cnt);
            ist[fr]=0;
            link(fa[u],to);
            ist[cnt]=1,fa[to]=fa[u];
            mp2[w[u]]=to;
        }
        else mp2[w[u]]=u;
    }
    void dfs(int u,int fr){
        dfn[u]=++dfu;
        int siz=v[u].size();
        for(int i=0;i<siz;i++){
            int to=v[u][i].first,id=v[u][i].second;
            if(id==fr||cut0[id]) continue;
            if(dfn[to]){
                if(dfn[to]>dfn[u]) continue;
                ll val=Rnd();
                w[u]^=val,w[to]^=val;
                mp1[val]=1;
            }
            else{
                ist[id]=1,fa[to]=u;
                dfs(to,id),w[u]^=w[to]; 
            }
        }
        if(fr&&mp1.count(w[u])) cut[fr]=1;
        if(cut[fr]||!fr){
            mp2.clear();
            dfs2(u,0);
            ++Cnt,dfs3(u,0,0,Cnt);
        }
    }
    void threecon(){
        for(int i=1;i<=n;i++)
            if(!dfn[i]) dfs(i,0);
    }

    namespace connected{//缩边三后圆方树 
        int n,cnt;//圆点1~n  方点n+1~n+cnt 
        vector<int>g[N];
        void linkg(int x,int y){
            g[x].push_back(y);
            g[y].push_back(x);
        }
        void buildgraph(){
            for(int i=1;i<=m;i++)
                if(col[ex[i]]!=col[ey[i]])
                    linkg(col[ex[i]],col[ey[i]]);
        }
        vector<int>tr[N*2];
        void link(int x,int y){
            tr[x].push_back(y);
            tr[y].push_back(x);
        }
        int top,dfu,stk[N],dfn[N],low[N],len[N];
        void dfs(int u,int fa){
            stk[++top]=u,low[u]=dfn[u]=++dfu;
            for(int to:g[u]){
                if(to==fa) continue;
                if(!dfn[to]){
                    len[to]=len[u]+1;
                    dfs(to,u),low[u]=min(low[u],low[to]);
                    if(low[to]>=dfn[u]){
                        cnt++;
                        while(stk[top+1]!=to) link(n+cnt,stk[top--]);
                        link(n+cnt,u);
                    }
                }
                else low[u]=min(low[u],dfn[to]);
            }
        }
        int dep[N*2],f[21][N*2],nid[N*2];
        void dfs2(int u,int fa){
            dep[u]=dep[fa]+1,f[0][u]=fa;
            for(int i=0;i<=19;i++)
                f[i+1][u]=f[i][f[i][u]];
            auto it=find(tr[u].begin(),tr[u].end(),fa);
            if(it!=tr[u].end()) tr[u].erase(it);
            if(u>n){//方点处理环 
                sort(tr[u].begin(),tr[u].end(),[&](int x,int y){
                    return len[x]<len[y];
                });
                for(int i=0;i<tr[u].size();i++) nid[tr[u][i]]=i+1;
            }
            for(int to:tr[u]) dfs2(to,u);
        }
        int LCA(int x,int y){
            if(dep[x]<dep[y]) swap(x,y);
            for(int i=20;i>=0;i--)
                if(dep[f[i][x]]>=dep[y]) x=f[i][x];
            if(x==y) return x;
            for(int i=20;i>=0;i--)
                if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
            return f[0][x];
        }
        int jump(int u,int jmp){
            for(int i=20;i>=0;i--)
                if(jmp>=(1<<i)) u=f[i][u],jmp-=(1<<i);
            return u;
        }
        struct node{
            int l,r,v;
            node(int x,int y){l=min(x,y),r=max(x,y),v=1;}
            node(int x,int y,int z){l=x,r=y,v=z;}
        };
        struct SGtree{//区间加区间max线段树 
            pair<int,int>tr[N*8];
            int tag[N*8];
            void adt(int x,int v){
                tag[x]+=v,tr[x].first+=v;
            }
            void pushdown(int id){
                if(tag[id]) adt(id*2,tag[id]),
                    adt(id*2+1,tag[id]),tag[id]=0;
            }
            void pushup(int id){
                tr[id]=max(tr[id*2],tr[id*2+1]);
            }
            #define mid ((l+r)>>1)
            void build(int id,int l,int r){
                tag[id]=0;
                if(l==r){tr[id]={0,l};return ;}
                build(id*2,l,mid);
                build(id*2+1,mid+1,r);
                pushup(id);
            }
            void modify(int id,int l,int r,int x,int y,int k){
                if(x>y) return ;
                if(x<=l&&r<=y){adt(id,k);return ;}
                pushdown(id);
                if(x<=mid) modify(id*2,l,mid,x,y,k);
                if(mid+1<=y) modify(id*2+1,mid+1,r,x,y,k);
                pushup(id);
            }
            pair<int,int>query(int id,int l,int r,int x,int y){
                if(x>y) return {-inf,0};
                if(x<=l&&r<=y) return tr[id];
                pushdown(id);
                if(y<=mid) return query(id*2,l,mid,x,y);
                if(mid+1<=x) return query(id*2+1,mid+1,r,x,y);
                return max(query(id*2,l,mid,x,y),query(id*2+1,mid+1,r,x,y));
            }
            #undef mid
        }T;
        int cro[N*2];
        vector<node>jnt[N*2],vx[N*2];
        void dfs3(int u){
            for(int to:tr[u])
                dfs3(to),cro[u]+=cro[to];
            if(u>n){
                for(int to:tr[u])
                    jnt[u].push_back({0,nid[to],cro[to]});
            }
        }
        vector<int>work(int id){
            int siz=tr[id].size()+1;
            int res=0,a=0,b=0,c=0,d=0;
            if(siz==2){
                for(auto [l,r,v]:jnt[id]) res+=v;
                a=c=f[0][id],b=d=tr[id][0];
                return {res,a,b,c,d};
            }
            T.build(1,0,siz-1);
            for(int i=0;i<siz;i++) vx[i].clear();
            for(auto [l,r,v]:jnt[id]){
                T.modify(1,0,siz-1,l,r-1,v);
                vx[l].push_back({0,l-1,v});
                vx[l].push_back({l,r-1,-v});
                vx[l].push_back({r,siz-1,v});
                vx[r].push_back({0,l-1,-v});
                vx[r].push_back({l,r-1,v});
                vx[r].push_back({r,siz-1,-v});
            }
            for(int i=0;i<siz-1;i++){
                for(auto [l,r,v]:vx[i]) T.modify(1,0,siz-1,l,r,v);
                auto rs=T.query(1,0,siz-1,i+1,siz-1);
                if(rs.first>res){
                    res=rs.first;
                    if(i==0) a=f[0][id],b=tr[id][0];
                    else a=tr[id][i-1],b=tr[id][i];
                    if(rs.second==siz-1) c=tr[id][siz-2],d=f[0][id];
                    else c=tr[id][rs.second-1],d=tr[id][rs.second];
                }
            }
            return {res,a,b,c,d};
        }
        vector<int>solve(){
            buildgraph();
            dfs(1,0),dfs2(1,0);
            for(int i=1;i<=K;i++){
                int x=col[a[i]],y=col[b[i]];
                if(x==y) continue;
                if(dep[x]>dep[y]) swap(x,y);
                int lca=LCA(x,y);
                if(lca==x) cro[x]--,cro[y]++;
                else{
                    cro[x]++,cro[y]++;
                    x=jump(x,dep[x]-dep[lca]-1);
                    y=jump(y,dep[y]-dep[lca]-1);
                    cro[x]--,cro[y]--;
                    jnt[lca].push_back(node(nid[x],nid[y]));
                }
            }
            dfs3(1);
            int ans=0,a=0,b=0,c=0,d=0;
            for(int id=n+1;id<=n+cnt;id++){
                auto res=work(id);
                if(res[0]>ans) ans=res[0],a=res[1],b=res[2],c=res[3],d=res[4];
            }
            vector<pair<int,int>>e;
            for(int i=1;i<=m;i++){
                int x=col[ex[i]],y=col[ey[i]];
                if((x==a&&y==b)||(x==b&&y==a)) e.push_back({ex[i],ey[i]});
                else if((x==c&&y==d)||(x==d&&y==c)) e.push_back({ex[i],ey[i]});
            }
            e.push_back({0,0});
            e.push_back({0,0});
            return {ans,e[0].first,e[0].second,e[1].first,e[1].second};
        }
        void Clear(){
            for(int i=1;i<=n;i++)
                stk[i]=dfn[i]=low[i]=len[i]=0,g[i].clear();
            for(int i=1;i<=n+cnt;i++){
                jnt[i].clear(),vx[i].clear();
                cro[i]=0,tr[i].clear();
            }
            dfu=top=n=cnt=0;
        }
    };
    vector<int>solve(){
        threecon();
        connected::n=Cnt;
        return connected::solve();
    }
    void Clear(){
        mp1.clear(),mp2.clear();
        connected::Clear();
        for(int i=1;i<=cnt;i++){
            ist[i]=cut0[i]=cut[i]=0;
        }
        for(int i=1;i<=n;i++) dfn[i]=fa[i]=col[i]=w[i]=0;
        dfu=Cnt=0;
    }
};
void Clear(){
    part1::Clear();
    part2::Clear();
    cnt=0;
    for(int i=1;i<=n;i++) v[i].clear();
}
void print(vector<int>r){
    cout<<r[0]<<"\n";
    int a=r[1],b=r[2],c=r[3],d=r[4];
    if(a>b) swap(a,b);
    if(c>d) swap(c,d);
    if((a==0||b==0)&&(c==0||d==0)){
        cout<<ex[1]<<" "<<ey[1]<<"\n"<<ex[2]<<" "<<ey[2]<<"\n";
        return ;
    }
    if((a==0)||(b==0)) swap(a,c),swap(b,d);
    if((a==c&&b==d)||(c==0||d==0)){
        for(int i=1;i<=m;i++)
          if(ex[i]==a&&ey[i]==b);
          else{c=ex[i],d=ey[i];break;}
    }
    cout<<a<<" "<<b<<"\n"<<c<<" "<<d<<"\n";
}
int main(){
    cin>>Gr>>g;
    while(Gr--){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&ex[i],&ey[i]);
            if(ex[i]>ey[i]) swap(ex[i],ey[i]);
            link(ex[i],ey[i]);
        }
        cin>>K;
        for(int i=1;i<=K;i++){
            scanf("%d%d",&a[i],&b[i]);
        }
        vector<int>r1=part1::solve();
        for(int i=1;i<=m;i++)
            part2::cut0[i]=part1::cut0[i];
        vector<int>r2=part2::solve();
        if(r1[0]>r2[0]) print(r1);
        else print(r2);
        Clear();
    }
    return 0;
}

::::