题解：CF2133E I Yearned For The Mines

TTpandaS · 2025-08-25 21:17:09 · 题解

这是一篇使用 dp 的题解。笔者在赛时因为写的代码过于狗屎导致没能在赛时调出代码。

如果不进行 2 操作，那么能找到当且仅当是一条链，从链头查到链尾。所以现在需要用小于等于 \dfrac{n}{4} 次 2 操作使得树变成若干条链。

令 f_{x,0/1/2} 表示 x 不断且父亲不断，断，不断且父亲断的最小断点数量。

转移是容易的，f_{x,1} 对于儿子可以任意方案，f_{x,0} 最多一个儿子不断，f_{x,2} 最多两个儿子不断。

代码难点在于输出方案。重新跑一次 DP 并同时记录当前点的方案为 0/1/2，为 1 则递归每个儿子的最优方案，为 0 则优先递归不断的儿子，为 2 的话需要额外一个 dfs 找到不断的两个儿子对应的两条链。

难点在于实现：

#include<bits/stdc++.h>
using namespace std;
int Tim=1;
const int N=2e5+5;
const int inf=1e9;
int n;
vector<int> g[N];
int son[N],f[N][3];
vector<int> ans;
bool vis[N];
bool ok[N];
void init(int n){
    for(int i=0;i<=n;i++){
        g[i].clear();
        vis[i]=0;
        ok[i]=0;
    }
    ans.clear();
}
void dfs1(int x,int fa){
    son[x]=0;
    for(int y:g[x]){
        if(y==fa){
            continue;
        }
        son[x]++;
        dfs1(y,x);
    }
    if(!son[x]){
        f[x][0]=0;
        f[x][1]=1;
        f[x][2]=inf;
        return;
    }
    f[x][0]=0;
    f[x][1]=1;
    f[x][2]=inf;
    int minn1=inf,minn2=inf;
    for(int y:g[x]){
        if(y==fa){
            continue;
        }
        f[x][1]+=min(f[y][0],min(f[y][1],f[y][2]));
        f[x][0]+=f[y][1];
        if(f[y][0]-f[y][1]<=minn1){
            minn2=minn1;
            minn1=f[y][0]-f[y][1];
        }
        else if(f[y][0]-f[y][1]<=minn2){
            minn2=f[y][0]-f[y][1];
        }
    }
    if(son[x]>=2){
        f[x][2]=f[x][0];
        f[x][2]+=minn1+minn2;
    }
    if(minn1<=0){
        f[x][0]+=minn1;
    }
    // cerr<<x<<':'<<f[x][0]<<' '<<f[x][1]<<' '<<f[x][2]<<'\n';
}
vector<int> now;
void dfs3(int x,int fa){
    now.push_back(x);
    ok[x]=1;
    int minn1=inf,pos1=0;
    for(int y:g[x]){
        if(y==fa){
            continue;
        }
        if(f[y][0]-f[y][1]<=minn1){
            minn1=f[y][0]-f[y][1];
            pos1=y;
        }
    }
    if(pos1&&minn1<=0){
        dfs3(pos1,x);
    }
}
void dfs2(int x,int fa,int op){
    // cerr<<x<<' '<<fa<<' '<<op<<' '<<ok[x]<<'\n';
    if(ok[x]){
        int minn1=inf,pos1=0;
        for(int y:g[x]){
            if(y==fa){
                continue;
            }
            if(f[y][0]-f[y][1]<=minn1){
                minn1=f[y][0]-f[y][1];
                pos1=y;
            }
        }
        if(minn1<=0){
            dfs2(pos1,x,0);
            for(int y:g[x]){
                if(y==fa||y==pos1){
                    continue;
                }
                dfs2(y,x,1);
            }           
        }
        else{
            for(int y:g[x]){
                if(y==fa){
                    continue;
                }
                dfs2(y,x,1);
            }
        }
    }
    else if(op==0){
        ans.push_back(x);
        int minn1=inf,pos1=0;
        for(int y:g[x]){
            if(y==fa){
                continue;
            }
            if(f[y][0]-f[y][1]<=minn1){
                minn1=f[y][0]-f[y][1];
                pos1=y;
            }
        }
        if(son[x]){
            if(minn1<=0){
                dfs2(pos1,x,0);
                for(int y:g[x]){
                    if(y==fa||y==pos1){
                        continue;
                    }
                    dfs2(y,x,1);
                }                   
            }
            else{
                for(int y:g[x]){
                    if(y==fa){
                        continue;
                    }
                    dfs2(y,x,1);
                }
            }
        }
    }
    else if(op==1){
        vis[x]=1;
        ans.push_back(x);
        for(int y:g[x]){
            if(y==fa){
                continue;
            }
            int mi=min(f[y][0],min(f[y][1],f[y][2]));
            if(f[y][0]==mi){
                dfs2(y,x,0);
            }
            else if(f[y][1]==mi){
                dfs2(y,x,1);
            }
            else{
                dfs2(y,x,2);
            }
        }
    }
    else if(op==2){
        int minn1=inf,pos1=0,minn2=inf,pos2=0;
        for(int y:g[x]){
            if(y==fa){
                continue;
            }
            if(f[y][0]-f[y][1]<=minn1){
                minn2=minn1;
                pos2=pos1;
                minn1=f[y][0]-f[y][1];
                pos1=y;
            }
            else if(f[y][0]-f[y][1]<=minn2){
                minn2=f[y][0]-f[y][1];
                pos2=y;
            }
        }
        now.clear();
        dfs3(pos1,x);
        reverse(now.begin(),now.end());
        for(int y:now){
            ans.push_back(y);
        }
        ans.push_back(x);
        now.clear();
        dfs3(pos2,x);
        for(int y:now){
            ans.push_back(y);
        }
        dfs2(pos1,x,0);
        dfs2(pos2,x,0);
        for(int y:g[x]){
            if(y==fa||y==pos1||y==pos2){
                continue;
            }
            dfs2(y,x,1);
        }
    }
}
void Solve(){
    cin>>n;
    init(n);
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(1,0);
    int mi=min(f[1][0],min(f[1][1],f[1][2]));
    // cerr<<"mi:"<<f[1][0]<<' '<<f[1][1]<<' '<<f[1][2]<<'\n';
    if(f[1][0]==mi){
        dfs2(1,0,0);
    }
    else if(f[1][1]==mi){
        dfs2(1,0,1);
    }
    else if(f[1][2]==mi){
        dfs2(1,0,2);
    } 
    int tot=0;
    for(int i=1;i<=n;i++){
        if(vis[i]){
            tot++;
        }
    }
    cout<<tot+n<<'\n';
    for(int i=1;i<=n;i++){
        if(vis[i]){
            cout<<2<<' '<<i<<'\n';
        }
    }
    for(int x:ans){
        cout<<1<<' '<<x<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>Tim;
    while(Tim--){
        Solve();
    }   
    return 0;
}