【Codeforces 786E】ALT | Mrsrz's blog

最小割，倍增优化建图

题目大意：

有一棵 $n$ 个点的树，每条路径上都有一个守卫。

有 $m$ 个人，第 $i$ 个人从 $u_i$ 走到 $v_i$。

现在要给一些人和守卫发宠物，要求一个人要么他自己发到宠物，要么他走的路径上的所有守卫都发到宠物。

求最少的发的宠物个数满足条件，并输出方案。

题解：

最小割模型。

对每个人和每条树边都建一个点。

源点向每个人连容量 $1$ 的边，每条树边向汇点连容量 $1$ 的边。每个人向他要走到的所有边连容量 $+\infty$ 的边。

不难理解，当源点和汇点不连通时，满足题目条件。我们的目标是删掉最少的边。这就是标准的最小割。

边数是 $O(nm)$ 的显然不能跑。考虑优化建图。

我们在树上倍增，每个点拆成 $\log n$ 个点，分别覆盖了它在内的向上 $1,2,2^2,2^3,\cdots$ 条边。

然后对每个人，将他的路径在 LCA 处分成两条路径，这两条路径分别可以被不超过 $2$ 条倍增区间覆盖（由于容量设为无穷所以不可能割这里的边，两个区间相交并无影响）。

那么我们得到的新图有 $n\log n+m$ 个点和 $n\log n+4m$ 条边。

可以直接跑最大流。

这里还要输出方案。

我们知道，最小割中的边一定满流。因此我们从源点开始 dfs，只走没满流的边，并标记被 dfs 到的点。则图被分成两部分，一部分被访问过，一部分没被访问过。其中间那些边就是一个最小割。由于反向弧的存在，这样做是对的。

然后，如果一个人代表的点没被访问过，则说明他所属那条边被割了。如果一条树边代表的点被访问过，则说明它所属那条边被割了。

Code：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int M=2e6+5,N=2e4+2,inf=0x3f3f3f3f;
int head[M],cnt=1,n,m,F[15][N],dep[M],nod,T;
int id_f[15][N],id_p[N],id_e[N];
bool vis[M];
int iter[M];
vector<int>G[N];
vector<int>id[N];
struct edge{
    int to,nxt,cap;
}e[M*3];
inline void addedge(int u,int v,int cap){
    e[++cnt]=(edge){v,head[u],cap},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0},head[v]=cnt;
}
void dfs(int now){
    for(int i=0;i<G[now].size();++i)
    if(!dep[G[now][i]]){
        int to=G[now][i];
        dep[to]=dep[now]+1;
        F[0][to]=now;
        id_e[to]=id[now][i];
        dfs(to);
    }
}
inline int LCA(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=14;~i;--i)
    if(dep[F[i][u]]>=dep[v])u=F[i][u];
    if(u==v)return u;
    for(int i=14;~i;--i)
    if(F[i][u]!=F[i][v])u=F[i][u],v=F[i][v];
    return F[0][u];
}
void link(int u,int v,int x){
    int w=0;
    for(int i=0;i<14;++i)
    if(dep[F[i][u]]>=dep[v])w=i;else break;
    addedge(x,id_f[w][u],inf);
    if(F[w][u]==v)return;
    int d=dep[F[w][u]]-dep[v];
    for(int i=14;~i;--i)
    if(d>>i&1)u=F[i][u];
    addedge(x,id_f[w][u],inf);
}
queue<int>q;
void bfs(){
    dep[0]=1;
    for(q.push(0);!q.empty();){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        if(e[i].cap&&!dep[e[i].to]){
            dep[e[i].to]=dep[u]+1;
            q.push(e[i].to);
        }
    }
}
int DFS(int u,int f){
    if(u==T||!f)return f;
    for(int&i=iter[u];i;i=e[i].nxt)
    if(e[i].cap&&dep[e[i].to]>dep[u]){
        int d=DFS(e[i].to,min(f,e[i].cap));
        if(d){
            e[i].cap-=d,e[i^1].cap+=d;
            return d;
        }
    }
    return 0;
}
int dinic(){
    for(int flow=0;;){
        memset(dep,0,(T+2)<<2);
        bfs();
        if(!dep[T])return flow;
        memcpy(iter,head,(T+2)<<2);
        for(int f;f=DFS(0,inf);flow+=f);
    }
}
void DfS(int u){
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    if(e[i].cap&&!vis[e[i].to])DfS(e[i].to);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v),G[v].push_back(u);
        id[u].push_back(i),id[v].push_back(i);
    }
    dfs(dep[1]=1);
    for(int i=1;i<=n;++i)id_f[0][i]=i;
    for(int i=n+1;i<=n+m;++i)id_p[i-n]=i;
    nod=n+m;
    for(int i=1;i<15;++i)
    for(int j=1;j<=n;++j){
        F[i][j]=F[i-1][F[i-1][j]];
        if(!F[i][j])continue;
        id_f[i][j]=++nod;
        addedge(nod,id_f[i-1][j],inf);
        addedge(nod,id_f[i-1][F[i-1][j]],inf);
    }
    T=++nod;
    for(int i=1;i<=m;++i)addedge(0,id_p[i],1);
    for(int i=2;i<=n;++i)addedge(id_f[0][i],T,1);
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        int lca=LCA(u,v);
        link(u,lca,id_p[i]),link(v,lca,id_p[i]);
    }
    int ans=dinic();
    cout<<ans<<'\n';
    DfS(0);
    vector<int>vec;
    for(int i=1;i<=m;++i)
    if(!vis[id_p[i]])vec.push_back(i);
    cout<<vec.size();
    for(int i:vec)cout<<' '<<i;
    cout<<'\n';
    vec.clear();
    for(int i=2;i<=n;++i)
    if(vis[id_f[0][i]])vec.push_back(id_e[i]);
    cout<<vec.size();
    for(int i:vec)cout<<' '<<i;
    cout<<'\n';
    return 0;
}