题解：P17122 [ICPC 2025 Shanghai R] Hamu

lailai0916 · 2026-08-30 23:48:16 · 题解

题意简述

给定无向多重图与起点 s，构造一条从 s 出发并回到 s 的闭合游走。游走中到达城市 i 的次数需要与 a_i 同奇偶，路线长度不能超过 5n。图中允许重边和自环。

解题思路

只需保留每个 a_i 的奇偶性。先从 s 广度优先搜索，得到所在连通块的一棵生成树，同时记录父亲、深度与黑白染色。

游走始终位于 s 的连通块。若块外存在 a_i 为奇数的城市，它不可能在本次旅行中被访问奇数次，所以无解。

再考虑连通块内目标奇偶向量中 1 的数量。所有到达次数之和等于游走长度。如果这个连通块是二分图，任意闭合游走长度均为偶数，目标向量中 1 的数量也必须为偶数。

若目标向量中有奇数个 1，必须先利用一个奇环。广度优先搜索时，连接两个同色结点的边与生成树路径组成奇环，自环则直接构成长为 1 的奇环。若不存在同色边，连通块是二分图，此时无解。

设找到的同色边为 (u,v)。路线从 u 经过该边到 v，再沿生成树上的简单路径回到 u，就走完一个奇环。环上的每个城市恰好被到达一次，因此可以先翻转这些城市的目标奇偶性。奇环长度为奇数，翻转后目标向量中 1 的数量变为偶数。之后只需在生成树上完成新的目标。

先考虑生成树的标准环游：从 s 出发，每条树边向下经过一次，再向上经过一次，最终回到 s。这条路线长度为 2(c-1)，其中 c 是连通块大小。根据树的儿子数量，可以直接算出标准环游对每个城市产生的到达次数奇偶性。

按照广度优先顺序的逆序处理每个非根结点 x。若当前奇偶性与目标不同，就在最后从 x 回到父亲之前加入一次额外折返：

相较于标准环游，这两步会分别多到达父亲和 x 一次，所以同时翻转两者的奇偶性。此时 x 被永久修正，变化只传给尚未处理的父亲。按深度从大到小处理后，所有非根结点都会满足目标。

根结点也必然正确。翻转奇环后，目标向量中有偶数个 1。树的标准环游和每次额外折返长度都是偶数，所以实际到达奇偶向量中也有偶数个 1。两者已经在所有非根结点处相同，根处不可能不同。

最后再次非递归遍历生成树，依次输出标准环游，并在对应结点离开前插入已经确定的折返。若使用了奇环，就在路线第一次到达 u 时插入完整的奇环序列。

奇环长度至多为 c，标准环游长度为 2(c-1)，每个非根结点至多增加一次长度为 2 的折返。总长度至多为：

广度优先搜索、奇环恢复与路线构造都只线性处理结点和边。时间复杂度为 O(n+m)，空间复杂度为 O(n+m)。

正确性证明

若目标为奇的城市不在 s 的连通块内，任何游走都无法访问它，故无解。若连通块是二分图，闭合游走长度为偶数，到达次数奇偶向量中的 1 也只能有偶数个。因此算法报告无解的两种情况都是必要条件。

连接同色结点的边与树上路径长度奇偶相同，再加一条边后得到奇环。沿该环一周会把环上每个城市的到达奇偶性翻转一次，使目标向量中 1 的总数改变奇数次。原总数为奇数时，新的总数便为偶数。

在生成树环游中，额外折返 x\to fa_x\to x 只相对原路线增加对 fa_x 与 x 的一次到达。逆序处理时，结点 x 的所有后代已经固定，折返不会再影响它们。算法据此修正 x，并把唯一影响传向父亲，所以归纳可知全部非根结点最终正确。根结点由两份奇偶向量的总异或均为零而自动正确。

奇环和所有树上动作都沿输入道路移动，拼接点也与当前所在城市一致，故输出始终是一条从 s 出发并回到 s 的合法游走。长度已经证明不超过 5n。因此，只要算法输出 Yes，给出的路线就满足全部要求；结合无解条件，算法正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
int a[N],fa[N],dep[N],col[N];
bool cur[N],add[N];
vector<int>G[N],son[N];
int lca(int x,int y)
{
    while(dep[x]>dep[y])x=fa[x];
    while(dep[y]>dep[x])y=fa[y];
    while(x!=y)
    {
        x=fa[x];
        y=fa[y];
    }
    return x;
}
vector<int> get_cycle(int x,int y)
{
    if(x==y)return {x};
    int z=lca(x,y);
    vector<int>res={y},p;
    for(int i=y;i!=z;i=fa[i])res.push_back(fa[i]);
    for(int i=x;i!=z;i=fa[i])p.push_back(i);
    reverse(p.begin(),p.end());
    for(auto i:p)res.push_back(i);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n,m,s;
        cin>>n>>m>>s;
        for(int i=1;i<=n;i++)
        {
            G[i].clear();
            son[i].clear();
            fa[i]=-1;
            cin>>a[i];
            a[i]&=1;
        }
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        vector<int>ord;
        queue<int>que;
        int u=0,v=0;
        fa[s]=0;
        dep[s]=col[s]=0;
        ord.push_back(s);
        que.push(s);
        while(que.size())
        {
            int x=que.front();
            que.pop();
            for(auto y:G[x])
            {
                if(fa[y]==-1)
                {
                    fa[y]=x;
                    dep[y]=dep[x]+1;
                    col[y]=col[x]^1;
                    son[x].push_back(y);
                    ord.push_back(y);
                    que.push(y);
                }
                else if(!u&&col[x]==col[y])
                {
                    u=x;
                    v=y;
                }
            }
        }
        bool ok=1;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]&&fa[i]==-1)ok=0;
            if(a[i]&&fa[i]!=-1)sum^=1;
        }
        vector<int>cyc;
        if(ok&&sum)
        {
            if(!u)ok=0;
            else
            {
                cyc=get_cycle(u,v);
                for(auto x:cyc)a[x]^=1;
            }
        }
        if(!ok)
        {
            cout<<"No"<<'\n';
            continue;
        }
        for(auto x:ord)
        {
            cur[x]=x!=s;
            add[x]=0;
        }
        for(int i=1;i<ord.size();i++)cur[fa[ord[i]]]^=1;
        for(int i=ord.size()-1;i>=1;i--)
        {
            int x=ord[i];
            if(cur[x]!=a[x])
            {
                add[x]=1;
                cur[x]^=1;
                cur[fa[x]]^=1;
            }
        }
        vector<int>ans;
        vector<pair<int,int>>st={{s,0}};
        bool used=cyc.empty();
        while(st.size())
        {
            int x=st.back().first;
            if(!used&&x==u)
            {
                for(auto y:cyc)ans.push_back(y);
                used=1;
            }
            if(st.back().second<son[x].size())
            {
                int y=son[x][st.back().second++];
                ans.push_back(y);
                st.push_back({y,0});
            }
            else
            {
                st.pop_back();
                if(x==s)continue;
                if(add[x])
                {
                    ans.push_back(fa[x]);
                    ans.push_back(x);
                }
                ans.push_back(fa[x]);
            }
        }
        cout<<"Yes"<<'\n'<<ans.size()<<'\n';
        for(auto x:ans)cout<<x<<' ';
        cout<<'\n';
    }
    return 0;
}