Zero xor#11795
Problem Author: | Kostiantyn Denysov |
Prepared by: | Kostiantyn Denysov, Maksym Shvedchenko |
Editorial by: | Kostiantyn Denysov |
Finding the Maximum Independent Set
First, we find the maximum independent set of the graph. You can do it greedily on the tree: take any leaf to the independent set and remove parent from the tree. If its size exceeds , a non-empty subset with a zero XOR can be chosen. This can be done using an XOR basis or even the meet-in-the-middle method without using a basis.
Constraint on the Size of the Maximum Independent Set
Next, consider the case when the size of the maximum independent set does not exceed . We will upper bound the number of independent sets in a tree.
Let be the number of edges in the maximum matching of the tree. For each edge in the matching, there are three options for choosing an independent set (pick one of the vertices or none). There are n - 2k vertices outside the matching, and for them, there are two choices (include or not include). Therefore, the number of independent sets is bounded by: 3^k \cdot 2^{n - 2k} \leq 3^{n - k}
The tree is a bipartite graph, so n - k is also the size of the maximum independent set, hence: n - k \leq m \Rightarrow 3^{m} Even for m = 30, this gives a fairly large number.
Splitting a Vertex into Two Sets
To reduce the number of options, we will split the tree vertices into two sets such that the size of the maximum independent set in each set does not exceed (m+1)/2. We also need to ensure the minimum number of vertices in the first part that are adjacent to vertices in the second part (optimally, this number should be , although improvements are possible).
Using Meet-in-the-Middle
We iterate over all independent sets in each of the two parts of the tree. The number of such sets is bounded by 3^{m/2}, which for m = 30 is approximately 1.4 \times 10^7.
We check if there are any identical XORs in the first and second sets, matching adjacent vertices between the sets (or if there is a zero XOR in either set).
The time complexity of this algorithm is O(3^{m/2} \cdot m), which is acceptable for m \leq 30.
Tree Partitioning Algorithm
Select the root vertex and hang the tree.
Run a greedy algorithm to find the maximum independent set:
Pick a leaf.
If it can be included in the set, add it and exclude its parent.
Let the first type of vertices be those that are part of the maximum independent set found by the greedy algorithm.
Count – the number of first-type vertices in the subtree of vertex .
Start from a leaf (not the root) and move upwards:
If cnt[v] < m/2, move upwards.
Otherwise, split the subtree as follows:
Sort the subtrees by descending .
Greedily add the subtrees to the first set.
Add vertex (and its parent if it is of the first type) to the first set (if not adding it, the parent may become part of the maximum independent set in the second set).
If an overflow occurs, recursively repeat the algorithm in the corresponding subtree where the overflow happened.
With this approach, the size of the independent set that needs to be formed is reduced at least by half each time. The number of vertices that connect the two sets is limited to 6-8 vertices, which is a small number.
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = 1e6 + 11, inf = 1000111222;
vec<int> edge[max_n], gg;
inline int dfs (int v, int p = -1) {
int val = 0;
for (int to : edge[v]) {
if (to == p) {
continue;
}
val |= dfs(to, v);
}
if (!val) {
gg.pb(v);
return 1;
}
return 0;
}
int cnt[max_n], good[max_n];
inline int dfs2 (int v, int p = -1) {
int cur = 0;
for (int to : edge[v]) {
if (to == p) {
continue;
}
cur |= dfs2(to, v);
cnt[v] += cnt[to];
}
if (!cur) {
++cnt[v];
good[v] = 1;
return 1;
}
return 0;
}
int used[max_n];
int mx;
inline void mark (int v, int p) {
used[v] = 1;
for (int to : edge[v]) {
if (to == p) {
continue;
}
mark(to, v);
}
}
inline void go (int v, int p = -1) {
if (!mx) {
return;
}
for (int to : edge[v]) {
if (to == p) {
continue;
}
if (cnt[to] >= mx) {
go(to, v);
return;
}
}
if (good[v]) {
--mx;
if (p != -1) {
used[p] = 1;
}
}
used[v] = 1;
sort(all(edge[v]), [&] (int a, int b) {
return cnt[a] > cnt[b];
});
int b = -1;
for (int to : edge[v]) {
if (to == p) {
continue;
}
if (mx >= cnt[to]) {
mx -= cnt[to];
mark(to, v);
}
else {
b = to;
}
}
if (mx) {
go(b, v);
}
}
pair<vec<int>, vec<int> > two_sets (int n) {
vec<int> A, B;
mx = (len(gg) + 1) / 2;
dfs2(0);
go(0);
for (int i = 0; i < n; i++) {
if (used[i]) {
A.pb(i);
}
else {
B.pb(i);
}
}
return make_pair(A, B);
}
int save[max_n], bit[max_n], match[max_n];
vec<pii> nice_edge[2];
vec<int> other[2];
inline int find_matching (int v, int p = -1) {
int was = 0;
for (int to : edge[v]) {
if (to == p) {
continue;
}
int res = find_matching(to, v);
if (!res && used[to] == used[v] && !was) {
was = 1;
nice_edge[used[v]].pb({v, to});
match[v] = match[to] = 1;
}
}
return was;
}
struct node {
int x;
ll mask;
int care;
bool operator < (const node &y) const {
return x < y.x || x == y.x && care < y.care;
}
bool operator == (const node &y) const {
return x == y.x && care == y.care;
}
};
const int max_k = 14348907 + 11;
node have_xor[max_k];
ll mask_neigh[max_n];
int save_care[max_n];
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vec<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
--u, --v;
edge[u].pb(v);
edge[v].pb(u);
}
dfs(0);
if (len(gg) > m + 1) {
gg.resize(m + 1);
}
int k = len(gg) / 2;
int lft = len(gg) - k;
map <int, int> have;
for (int mask = 0; mask < (1 << k); mask++) {
int x = 0, cnt = 0;
for (int j = 0; j < k; j++) {
if (mask & (1 << j)) {
++cnt;
x ^= a[gg[j]];
}
}
if (x == 0 && mask) {
cout << "Yes\n";
cout << cnt << '\n';
for (int j = 0; j < k; j++) {
if (mask & (1 << j)) {
cout << gg[j] + 1 << ' ';
}
}
cout << '\n';
return 0;
}
have[x] = mask;
}
for (int mask = 0; mask < (1 << lft); mask++) {
int x = 0, cnt = 0;
for (int j = 0; j < lft; j++) {
if (mask & (1 << j)) {
++cnt;
x ^= a[gg[k + j]];
}
}
if (x == 0 && mask) {
cout << "Yes\n";
cout << cnt << '\n';
for (int j = 0; j < lft; j++) {
if (mask & (1 << j)) {
cout << gg[k + j] + 1 << ' ';
}
}
cout << '\n';
return 0;
}
if (x) {
if (have.count(x)) {
cout << "Yes\n";
int res = cnt + __builtin_popcount(have[x]);
cout << res << '\n';
for (int j = 0; j < lft; j++) {
if (mask & (1 << j)) {
cout << gg[k + j] + 1 << ' ';
}
}
for (int j = 0; j < k; j++) {
if (have[x] & (1 << j)) {
cout << gg[j] + 1 << ' ';
}
}
cout << '\n';
return 0;
}
}
}
assert(len(gg) <= m);
vec<int> A, B;
tie(A, B) = two_sets(n);
for (int i = 0, num = 0; i < n; i++) {
if (used[i]) {
bool ok = false;
for (int to : edge[i]) {
if (!used[to]) {
ok = true;
}
}
if (ok) {
save[i] = 1;
bit[i] = num++;
}
}
}
find_matching(0);
for (int i = 0; i < n; i++) {
if (!match[i]) {
other[used[i]].pb(i);
}
}
swap(nice_edge[0], nice_edge[1]);
swap(other[0], other[1]);
int num = 0;
for (int i = 0; i < n; i++) {
for (int to : edge[i]) {
mask_neigh[i] |= 1ll << to;
if (save[to]) {
save_care[i] |= 1 << bit[to];
}
}
}
{
int x = 1;
for (int i = 0; i < len(nice_edge[0]); i++) {
x *= 3;
}
vec<int> state(len(nice_edge[0]));
for (int mask1 = 0; mask1 < x; mask1++) {
ll mask_ver = 0, neigh_mask = 0;
int care_mask = 0, xx = 0;
for (int j = 0; j < len(nice_edge[0]); j++) {
int val = state[j];
if (val == 0) {
}
else if (val == 1) {
mask_ver |= 1ll << nice_edge[0][j].first;
neigh_mask |= mask_neigh[nice_edge[0][j].first];
xx ^= a[nice_edge[0][j].first];
if (save[nice_edge[0][j].first]) {
care_mask |= 1 << bit[nice_edge[0][j].first];
}
}
else if (val == 2) {
mask_ver |= 1ll << nice_edge[0][j].second;
neigh_mask |= mask_neigh[nice_edge[0][j].second];
xx ^= a[nice_edge[0][j].second];
if (save[nice_edge[0][j].second]) {
care_mask |= 1 << bit[nice_edge[0][j].second];
}
}
}
for (int j = 0; j < len(nice_edge[0]); j++) {
++state[j];
if (state[j] == 3) {
state[j] = 0;
}
else {
break;
}
}
if ((mask_ver & neigh_mask) > 0) {
continue;
}
for (int mask2 = 0; mask2 < (1 << len(other[0])); mask2++) {
ll cur_mask_ver = mask_ver;
ll cur_mask_neigh = neigh_mask;
int cur_care = care_mask, cur_x = xx;
for (int i = 0; i < len(other[0]); i++) {
if (mask2 & (1 << i)) {
cur_mask_ver |= 1ll << other[0][i];
cur_mask_neigh |= mask_neigh[other[0][i]];
cur_x ^= a[other[0][i]];
if (save[other[0][i]]) {
cur_care |= 1 << bit[other[0][i]];
}
}
}
if ((cur_mask_ver & cur_mask_neigh) > 0) {
continue;
}
if (cur_x == 0) {
if (cur_mask_ver) {
cout << "Yes\n" << __builtin_popcountll(cur_mask_ver) << '\n';
for (int i = 0; i < n; i++) {
if (cur_mask_ver & (1ll << i)) {
cout << i + 1 << ' ';
}
}
cout << '\n';
return 0;
}
continue;
}
have_xor[num++] = node{cur_x, cur_mask_ver, cur_care};
}
}
}
sort(have_xor, have_xor + num);
num = unique(have_xor, have_xor + num) - have_xor;
{
int x = 1;
for (int i = 0; i < len(nice_edge[1]); i++) {
x *= 3;
}
vec<int> state(len(nice_edge[1]));
for (int mask1 = 0; mask1 < x; mask1++) {
int y = mask1;
ll mask_ver = 0, neigh_mask = 0;
int care_mask = 0, xx = 0;
for (int j = 0; j < len(nice_edge[1]); j++) {
int val = state[j];
if (val == 0) {
}
else if (val == 1) {
mask_ver |= 1ll << nice_edge[1][j].first;
neigh_mask |= mask_neigh[nice_edge[1][j].first];
xx ^= a[nice_edge[1][j].first];
care_mask |= save_care[nice_edge[1][j].first];
}
else if (val == 2) {
mask_ver |= 1ll << nice_edge[1][j].second;
neigh_mask |= mask_neigh[nice_edge[1][j].second];
xx ^= a[nice_edge[1][j].second];
care_mask |= save_care[nice_edge[1][j].second];
}
}
for (int j = 0; j < len(nice_edge[1]); j++) {
++state[j];
if (state[j] == 3) {
state[j] = 0;
}
else {
break;
}
}
if ((mask_ver & neigh_mask) > 0) {
continue;
}
for (int mask2 = 0; mask2 < (1 << len(other[1])); mask2++) {
ll cur_mask_ver = mask_ver;
ll cur_mask_neigh = neigh_mask;
int cur_care = care_mask, cur_x = xx;
for (int i = 0; i < len(other[1]); i++) {
if (mask2 & (1 << i)) {
cur_mask_ver |= 1ll << other[1][i];
cur_mask_neigh |= mask_neigh[other[1][i]];
cur_x ^= a[other[1][i]];
cur_care |= save_care[other[1][i]];
}
}
if ((cur_mask_ver & cur_mask_neigh) > 0) {
continue;
}
if (cur_x == 0) {
if (cur_mask_ver) {
cout << "Yes\n" << __builtin_popcountll(cur_mask_ver) << '\n';
for (int i = 0; i < n; i++) {
if (cur_mask_ver & (1ll << i)) {
cout << i + 1 << ' ';
}
}
cout << '\n';
return 0;
}
continue;
}
int l = lower_bound(have_xor, have_xor + num, node{cur_x, -1, -1}) - have_xor;
while (l < num && have_xor[l].x == cur_x) {
if ((have_xor[l].care & cur_care) == 0) {
ll now = cur_mask_ver | have_xor[l].mask;
cout << "Yes\n" << __builtin_popcountll(now) << '\n';
for (int i = 0; i < n; i++) {
if (now & (1ll << i)) {
cout << i + 1 << ' ';
}
}
cout << '\n';
return 0;
}
++l;
}
}
}
}
cout << "No\n";
}
/*
KoRoVa!
*/