[ABC244] G - Construct Good Path

[Q] https://atcoder.jp/contests/abc244/tasks/abc244_g

Fとほぼ同じような問題設定なので、FとGが同じURLでバグってるのかと思った。

問題文を読むと、
「S に関する長さ 4N 以下の良いパスが少なくとも 1 つ存在することが示せます。」
4Nと特殊な指定があるので、貪欲ルールを発見するんだろうと思う。

そして、グラフが木だとしたら、葉っぱから貪欲に確定できそう。

1 - 2 - 3 - 4
という木について。

自分が2にいる場合。
1を奇数回踏みたかったら、2,1,2とすればいいし、
1を偶数回踏みたかったら、2,1,2,1,2とすればいいし、2, だけで1を踏まなくてもいい。

2にいるときに1を確定させて、
3にいるときに2を確定させて、
4にいるときに3を確定させる。

これは、1頂点あたり4手で確定できそう。

ということで、
1. グラフは木を張る。
2. DFSする。いったん深く潜る。
3. DFSで、戻るときに、葉側にある頂点の状態を確定させる。

実装

queue<ll> ans;
ll N, M;
string S;

void dfs(ll u, ll p, bool hash[100010]) {
 // いったん深く潜る
 for (auto v : G[u]) {
   if (v == p) continue;
   ans.push(v);
   hash[v] ^= 1;
   dfs(v, u, hash);
 }
 // 戻る。
 if (p == -1) return;
 ans.push(p);
 hash[p] ^= 1;
 // u:pよりも葉に近い頂点。これが、Sと合致しないなら調整する。
 if ('0' + hash[u] != S[u]) {
   ans.push(u);
   ans.push(p);
   hash[u] ^= 1;
   hash[p] ^= 1;
 }
}

int main() {
 cincout();

 cin >> N >> M;
 // UnionFind
 G.assign(N + 1, vector<ll>());
 seen.assign(N + 1, false);
 UnionFind tree(N);
 rep(i, M) {
   ll u, v;
   cin >> u >> v;
   --u, --v;
   // 木を構成するN-1辺を採用する
   if (tree.issame(u, v)) continue;
   G[u].push_back(v);
   G[v].push_back(u);
   tree.unite(u, v);
 }
 cin >> S;

 bool hash[100010]{};
 hash[0] = true;
 ans.push(0);
 dfs(0, -1, hash);
 // スタート値0の偶奇が考慮できていないので処理。
 if ('0' + hash[0] != S[0]) {
   ans.pop();
 }
 cout << ans.size() << endl;
 while (!ans.empty()) {
   cout << ans.front() + 1;
   ans.pop();
   if (ans.empty())
     cout << endl;
   else
     cout << " ";
 }
}

https://atcoder.jp/contests/abc244/submissions/30302288