Atcoder Petrozavodsk Contest 001 F. XOR Tree

F - XOR Tree

解法

$XOR$ の性質を使ってかなりきれいに解けます。

まず、パスに関する操作が非常に扱いにくいため、なんとかしたい気持ちになります。

$XOR$ の性質で重要なものとして、任意の数について、それ自身との $XOR$ は$0$ になるというものがあります。これをうまく使えないでしょうか。

ここで、パスの自明な性質として、端の点の次数は $1$ で、途中の点の次数は $2$ であるという性質があります（それはそうで）。このことを考えると、通過するたびに $XOR$ の演算によって打ち消されていくような不変量のようなものを見つけることができそうです。

具体的には、次のようにします。すべての頂点について、その頂点 $v$ から伸びるすべての辺に書かれた数の $XOR$ を計算しておき、それを $a_v$ とおきます。すると、操作を行うパスの途中の点では、$x$ の $XOR$ を $2$ 回とることになり、打ち消しあうことになります。これで操作を、端点のみに任意の数 $x$ を $XOR$ として作用させる操作に置き換えることができました。この値 $a_i$ の値がすべて $0$ になったとき、さらにそのときに限り、題意をみたすことになります。

この置き換えのすごいところは、グラフが連結であるという前提から、もはやグラフの構造は全く気にしなくてよくなったことです。

さて、次にどの $2$ 点を選んでいくかについて考えていきます。この選んだ $2$ 点に辺を張ったグラフを考えてみると、実はこれは適切にやることで必ず森になることが示せます。閉路をつくるメリットがないことを述べればよいわけですが、それは次の図によって示すことができます。

$3$ 頂点に対して、画像左のように $3$ 本の辺を張るとします。この結果、それぞれの頂点に作用させる $XOR$ の値はそれぞれ $xy, yz, zx$ となっています。ところが、$XOR$ の性質より、画像右のような $2$ 本の辺で代用することができるはずです。よって閉路を作って得することはないことがわかり、森になることが示されました。

さて、辺を張って森を作ったとして、そのそれぞれの木に注目すると、（操作の回数はその連結成分のサイズ $-\ 1$） になるはずです。これを条件を満たす辺の張り方にできるかどうかは、実はその頂点に書かれた数のすべての $XOR$ が $0$ であるかどうかを確かめるだけでよいです。

これを示します。まず全体の $XOR$ の値が $0$ でない場合は、いくら操作を行っても $0$ にすることはできません。なぜなら、どんな操作もある $2$ 頂点に同一の値の $XOR$ を作用させることになるため、全体の $XOR$ は不変だからです。逆に、全体の $XOR$ が $0$ であれば、葉の方から順に $0$ にしていくことができるはずです。これで示されました。

これで木の集合として条件を満たすものがわかりました。よってすべての頂点をこの集合に分割することになりますが、もとから $0$ の頂点は無視してよく、$0$ ではない同じ数同士はサイズ $2$ の木として作ってしまった方がよいことがわかります。

これを繰り返すと、取りうる値は $0$ から $15$ であることから、$0$ を無視すると、高々 $k = 15$ 個の頂点のみが残ります。これはいわゆる部分集合を扱う $O(3^k)$ の $bitDP$ で計算できます。

以上でこの問題が解けました。

実装

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        vector<int> p(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b, c;
                scanf("%d %d %d", &a, &b, &c);
                p[a] ^= c;
                p[b] ^= c;
        }
        vector<int> cnt(16, 0);
        for (int i = 0; i < n; i ++) {
                cnt[p[i]] ++;
        }
        int ans = 0;
        int mask = 0;
        for (int i = 1; i < 16; i ++) {
                ans += cnt[i] / 2;
                if (cnt[i] & 1) {
                        mask |= 1 << i;
                }
        }
        vector<bool> ok(1 << 16, 0);
        for (int i = 0; i < (1 << 16); i ++) {
                int check = 0;
                for (int j = 0; j < 16; j ++) {
                        if (i & (1 << j)) {
                                check ^= j;
                        }
                }
                ok[i] = check == 0;
        }
        vector<int> dp(1 << 16, 0);
        for (int i = 0; i < (1 << 16); i ++) {
                if (i & 1) continue; //ignore the nodes whose value is already 0
                int sub = i; //subset of i
                while (sub > 0) {
                        if (ok[sub]) {
                                dp[i] = max(dp[i], dp[i ^ sub] + 1);
                        }
                        sub = (sub - 1) & i;
                }
        }
        printf("%d\n", ans + __builtin_popcount(mask) - dp[mask]);
        return 0;
}