自动搬运

查看原文

来自洛谷，原作者为

	SAMSHAWCRAFT 疠疫俾惊，荒时殆情。

搬运于2025-08-24 22:34:24，当前版本为作者最后更新于2021-12-20 22:12:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

分类讨论：

1. $\texttt{root}$ 和 $\texttt{rootbro}$ 都不染色。
2. $\texttt{root}$ 染色但 $\texttt{rootbro}$ 不染色。
3. $\texttt{root}$ 不染色但 $\texttt{rootbro}$ 染色。
4. $\texttt{root}$ 和 $\texttt{rootbro}$ 都染色。

树形 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）时需要染色的最少节点数，状态转移的时候只需要每一下子节点是否需要染色即可。

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

1. $\texttt{u}=\texttt{root}$ 但 $\texttt{rtc}\neq\texttt{th}$，即本来根应该染色但根没有被染色或本来根不该染色却被染色的情况。
2. $\texttt{u}=\texttt{rootbro}$ 但 $\texttt{rtbroc}\neq\texttt{th}$，即本来根的兄弟应该染色但根没有被染色或本来根的兄弟不该染色却被染色的情况。
3. $\texttt{u}=\texttt{rootbro}$ 且 $\texttt{fac}=1$ 且 $\texttt{rtc}=1$，即根的兄弟同时连接了两个被染色了的点。

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

#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;
}