G - Construct Good Path Editorial by en_translator
Suppose that the given graph is a rooted tree rooted at an arbitrary vertex \(r\). We will construct a good path with respect to \(S = s_1s_2\ldots s_N\), that is, for all vertex \(v\), “the parity of number of occurrences of \(v\) in \(A\)” and “the parity of \(s_v\)” are the same. If the given graph isn’t a tree, we can take an arbitrary spanning tree so that it is boiled down to the case of tree.
For every vertex \(v = 1, 2, \ldots, N\), we recursively define a sequence \(A_v\) as follows.
- If \(v\) does not have a child, then let \(A_v := (v)\), that is, \(A_v\) is a sequence of length \(1\) only consisting of \(v\).
- If \(A_v\) has children \(c_1, c_2, \ldots, c_k\), then let \(A_v := (v) + A_{c_1} + B_{c_1} + (v) + A_{c_2} + B_{c_2} + (v) + \cdots + (v) + A_{c_k} + B_{c_k} + (v)\).
Here, \(+\) denotes a concatenation of sequences, and sequence \(B_{c_i}\) is defined to be
- \(B_{c_i} := ()\) if “the parity of the number of occurrences of \(c_i\) in \(A_{c_i}\)” and “the parity of \(s_{c_i}\)” are equal, and
- \(B_{c_i} := (v, c_i)\) otherwise.
Then, for every vertex \(v = 1, 2, \ldots, N\), it can be proved by induction that \(A_v\) satisfies the following four statements.
- \(A_v\) is a path.
- \(A_v\) starts and ends with \(v\).
- The length of \(A_v\) is at most \(4n-3\), where \(n\) is the number of ancestors of \(v\) (including \(v\) itself).
- For every ancestor \(d\) of \(v\), except for \(v\) itself, “the parity of the number of occurrences of \(d\) in \(A_v\)” and “the parity of \(s_d\)” are equal.
Therefore, the sequence \(A_r\) corresponding to root \(r\) is a path of length at most \(4N-3\), ending with \(r\), and for every vertex \(v\) except for \(r\), “the parity of the number of occurrences of \(v\) in \(A_r\)” and “the parity of \(s_v\)” are equal.
Hence, the following sequence
- \(A_r\), if “the parity of the number of occurrences of \(r\) in \(A_r\)” and “the parity of \(s_r\)” are equal too; or
- \(A_r + (u, r, u)\), for an arbitrary vertex \(u\) adjacent to \(r\), if they are not equal;
is a good path with respect to \(S\) of length at most \(4N\). By printing this, you will be accepted for this problem.
The following is a sample code in C++ language.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> G[100005];
char s[100005];
bool used[100005];
vector<int> ans;
void dfs(int v)
{
used[v] = true;
ans.push_back(v), s[v] ^= 1;
for(auto u : G[v]){
if(used[u]) continue;
dfs(u);
ans.push_back(v), s[v] ^= 1;
if(s[u] == 1){
ans.push_back(u), s[u] ^= 1;
ans.push_back(v), s[v] ^= 1;
}
}
}
int main(void)
{
cin >> n >> m;
int u, v;
for(int i = 1; i <= m; i++){
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = 1; i <= n; i++) cin >> s[i], s[i] -= '0';
dfs(1);
if(s[1] == 1){
ans.push_back(G[1][0]);
ans.push_back(1);
ans.push_back(G[1][0]);
}
cout << ans.size() << endl;
for(auto x : ans) cout << x << " ";
cout << endl;
return 0;
}
posted:
last update: