[COCI2021-2022#1] Logičari - 题解

· · 题解

基环树，就是将一棵树的两个顶点用一条边 E 连起来形成的图。这个图上有且只有一个环，并且这个环上必定有上述的边 E。

现在我们有一颗基环树，要在上面染色。我们知道如果在一棵树上像题目中说的那样染色，可以用树形 DP 解决。而对于本题我们可以考虑把这个基环树的环切开，切口一端当作树根，另一端当作树根的“兄弟”，之后 DP，再看切口两侧染色的情况是否符合题意。

怎么确定切口？可以借助并查集，当一条边 E 的两个端点 u,v 在并查集中已经处于一个集合中，换言之是 u,v 已经在一棵树上，那么连接 u,v 的这条边 E 就是基环树上的环上的一条边，此时可以选 u 做树根（在代码中对应变量 \texttt{root}），v 做树根的“兄弟”（在代码中对应变量 \texttt{rootbro}），在建图时切断这条边其实等价于不连这条边，其余的普通的边只需正常连边即可。建图完成之后，分四类讨论，规约到树形 DP 问题上。

分类讨论：

树形 DP 的过程比较基础，设计状态 f(\texttt{u,th,fac,rtc,rtbroc}) 表示当前从 \texttt{root} 染色到节点 \texttt{u} 时，\texttt{u} 的染色状态为 \texttt{th}，而 \texttt{root} 和 \texttt{rootbro} 染色状态分别为 \texttt{rtc} 和 \texttt{rtbroc}（\texttt{th},\texttt{fac},\texttt{rtc},\texttt{rtbroc} 都是当且仅当被染色时为 1，否则为 0）时需要染色的最少节点数，状态转移的时候只需要每一下子节点是否需要染色即可。

无解的情况只有三种，特判一下：

细节较多，代码如下，仅供参考。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <numeric>
#define qaq inline
using ll=long long;
const int inf=1e9+7;
const int sz=1e5+19;
const int esz=2e5+19;
int n,head[sz],hpp=0,root,rootbro,ans;
struct edge{
    int nxt,to;
}graph[esz];
qaq void addEdge(int from,int to){
    graph[++hpp]=edge{head[from],to};
    head[from]=hpp;
}
struct UnionFindSet{
    int fa[sz];
    qaq void clear(int n=sz-1){
        for(int cx=0;cx<=n;++cx)
            fa[cx]=cx;
    }
    int findAnc(int id){
        if(fa[id]==id) return id;
        return fa[id]=findAnc(fa[id]);
    }
    qaq bool connect2(int u,int v){
        return findAnc(u)==findAnc(v);
    }
    qaq void join(int u,int v){
        int fu=findAnc(u);
        int fv=findAnc(v);
        if(fu==fv) return;
        fa[fu]=fv;
    }
}UFS;
int pr[sz];
void DFS(int u,int fau){
    pr[u]=fau;
    for(int p=head[u];p!=0;p=graph[p].nxt){
        int v=graph[p].to;
        if(v==fau) continue;
        DFS(v,u);
    }
}
int dp[sz][2][2][2][2];
int color(int u,int th,int fac,int rtc,int rtbroc){
    ///@param u: currently visited vertex
    ///@param th: equals to 1 only when u is colored
    ///@param fac: equals to 1 only when u's father is colored
    ///@param rtc: equals to 1 only when root is colored
    ///@param rtbroc: equals to 1 only when rootbro is colored
    if(dp[u][th][fac][rtc][rtbroc]!=-1)
        return dp[u][th][fac][rtc][rtbroc];
    ll res=inf;
    bool valid=true;
    if(u==root&&th!=rtc) valid=false;
    if(u==rootbro&&th!=rtbroc) valid=false;
    if(u==rootbro&&fac&&rtc) valid=false;
    if(!valid) return dp[u][th][fac][rtc][rtbroc]=inf;
    bool cfree=false;
    ///@param cfree: true only when u is not able to be colored
    if(fac) cfree=true;
    if(u==root&&rtbroc) cfree=true;
    if(u==rootbro&&rtc) cfree=true;
    ll ccnt=th;
    ///@param ccnt: the number of currently colored vertexes
    for(int p=head[u];p!=0;p=graph[p].nxt){
        int v=graph[p].to;
        if(v==pr[u]) continue;
        ccnt+=color(v,0,th,rtc,rtbroc);
    }
    if(cfree){
        res=std::min(res,ccnt);
    }else{
        for(int p=head[u];p!=0;p=graph[p].nxt){
            int v=graph[p].to;
            if(v==pr[u]) continue;
            res=std::min(res,ccnt-color(v,0,th,rtc,rtbroc)+color(v,1,th,rtc,rtbroc));
        }
    }
    return dp[u][th][fac][rtc][rtbroc]=res;
}
int main(){
    scanf("%d",&n);
    UFS.clear(n);
    memset(dp,-1,sizeof dp);
    for(int cx=1,u,v;cx<=n;++cx){
        scanf("%d%d",&u,&v);
        if(UFS.connect2(u,v)){
            root=u,rootbro=v;
        }else{
            UFS.join(u,v);
            addEdge(u,v);
            addEdge(v,u);
        }
    }
    DFS(root,0);
    int ans=inf;
    ans=std::min({ans,color(root,0,0,0,0),color(root,0,0,0,1),
                  color(root,1,0,1,0),color(root,1,0,1,1)});
    if(ans==inf) puts("-1");
    else printf("%d\n",ans);
    return 0;
}