题解：P13583 [NWRRC 2023] Colorful Village

littleKtian · 2025-08-11 19:54:48 · 题解

题意

有一个节点数为 2n 的树。每个节点有一个颜色，一共 n 种颜色，每种颜色各有 2 个对应节点。在树上找一个大小为 n 的连通块，要求其中恰好包含每种颜色的节点各 1 个。

思路

记 a_i 表示第 i 个节点是否被选入集合内，1 代表选入。

任意位置的连通块并不好做，所以我们考虑枚举第 1 种颜色所选的节点 u 强制加入集合内。令 u 为根，则连通块可以看作到根节点的连通性。

此时所有的要求条件可以看作如下集中限制：

• 强制 u 加入集合，即强制 a_u=1；
• 连通性：设 p 为 q(q\neq u) 在树上的父亲节点，则有 a_q=1\longrightarrow a_p=1 和 a_p=0\longrightarrow a_q=0；
• 每种颜色各 1 个节点：设 x 和 y 为颜色相同的两个节点，则有 a_x \oplus a_y=1。

上述限制都可以用 2-SAT 解决。

做两次 2-SAT 即可，时间复杂度 O(n)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,c[200005],w[100005][2],ans[100005],tot;
vector<int> edget[200005];
void addt(int u,int v){edget[u].push_back(v);}
vector<int> edge[400005];
void add(int u,int v){edge[u].push_back(v);}
void dfst(int u,int fa){
    for(int i=0,in=edget[u].size();i<in;i++){
        int v=edget[u][i];
        if(v!=fa)add(2*n+u,2*n+v),add(v,u),dfst(v,u);
    }
}
int lo[400005],xh[400005],dfn,h[400005],toth;
int z[400005],zd,us[400005];
void dfs(int u){
    lo[u]=xh[u]=++dfn,z[++zd]=u,us[u]=1;
    for(int i=0,in=edge[u].size();i<in;i++){
        int v=edge[u][i];
        if(!xh[v])dfs(v),lo[u]=min(lo[u],lo[v]);
        else if(us[v])lo[u]=min(lo[u],xh[v]);
    }
    if(lo[u]==xh[u]){
        ++toth;
        while(z[zd]!=u)h[z[zd]]=toth,us[z[zd]]=0,--zd;
        h[z[zd]]=toth,us[z[zd]]=0,--zd;
    }
}
bool sat(int x){
    for(int i=1;i<=4*n;i++)edge[i].clear();
    add(2*n+x,x);
    dfst(x,0);
    for(int i=1;i<=n;i++){
        int u=w[i][0],v=w[i][1];
        add(u,2*n+v),add(2*n+u,v);
        add(v,2*n+u),add(2*n+v,u);
    }
    for(int i=1;i<=4*n;i++)lo[i]=xh[i]=0;
    dfn=toth=0;
    for(int i=1;i<=4*n;i++)if(!xh[i])dfs(i);
    for(int i=1;i<=2*n;i++)if(h[i]==h[i+2*n])return false;
    tot=0;
    for(int i=1;i<=2*n;i++)if(h[i]<h[i+2*n])cout<<i<<' ';
    cout<<'\n';
    return true;
}
void work(){
    cin>>n;
    for(int i=1;i<=n;i++)w[i][0]=w[i][1]=0;
    for(int i=1;i<=2*n;i++){
        cin>>c[i];
        if(w[c[i]][0]==0)w[c[i]][0]=i;else w[c[i]][1]=i;
    }
    for(int i=1;i<=2*n;i++)edget[i].clear();
    for(int i=1;i<2*n;i++){
        int u,v;cin>>u>>v;
        addt(u,v),addt(v,u);
    }
    bool check;
    check=sat(w[1][0]);
    if(check)return;
    check=sat(w[1][1]);
    if(check)return;
    cout<<-1<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;cin>>T;
    while(T--)work();
}