note

木DP部分は自然にやればできたが、bit DPだけなぜか忘れていて気付けなかった (editorialを見た)。

solution

木DP。bit DP。$A = \max a_i$として$O(N A + 3^A A)$。

まず重みが辺に乗っているのが面倒。 そこで根をひとつ勝手に固定し、頂点に移してしまう。 そして $\mathrm{dp} : (\text{subtrees}) \to 2^{15}$ の形の木DPをする。 各部分木について、その部分木内から外へ出ていくような単純pathについての値$x$への操作があるかを求めていく。 複数の子から同じ値$x$のpathsが出てきたらこれを繋げて消し、それ以外では消さずすべて上へ持ち上げて最後に根の部分でbit DPして処理する。 xorなのでいい感じにやれば上手く行く。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;
template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }

int solve(int n, const vector<int> & x, const vector<int> & y, const vector<int> & a) {
    constexpr int MAX_A = 0xf;
    assert (*max_element(ALL(a)) <= MAX_A);

    // make the adjacent list
    vector<vector<int> > g(n);
    REP (i, n - 1) {
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }

    // fix a root
    vector<int> parent(n, -1);
    constexpr int root = 0; {
        function<void (int)> go = [&](int i) {
            for (int j : g[i]) if (j != parent[i]) {
                parent[j] = i;
                go(j);
            }
        };
        go(root);
    }

    // move labels to nodes
    vector<int> b(n, -1);
    REP (i, n - 1) {
        if (parent[x[i]] == y[i]) {
            b[x[i]] = a[i];
        } else if (x[i] == parent[y[i]]) {
            b[y[i]] = a[i];
        } else {
            assert (false);
        }
    }

    // tree dp
    int removed = 0;
    function<int (int)> go = [&](int i) {
        int cnt1 = 0;
        for (int j : g[i]) if (j != parent[i]) {
            int cnt2 = go(j);
            REP (x, MAX_A + 1) if (cnt2 & (1 << x)) {
                removed += (bool)(cnt1 & (1 << x));
                cnt1 ^= 1 << x;
            }
        }
        int k = b[i];
        if (k != -1) {
            REP (x, MAX_A + 1) if (cnt1 & (1 << x)) {
                k ^= x;
            }
            if (k != 0) {
                removed += (bool)(cnt1 & (1 << k));
                cnt1 ^= 1 << k;
            }
        }
        return cnt1;
    };
    int cnt = go(root);

    // finialize
    constexpr int INF = 1e9 + 7;
    vector<int> dp(1 << (MAX_A + 1), INF);
    dp[0] = 0;
    REP (s, 1 << (MAX_A + 1)) if ((s | cnt) == cnt) {
        for (int t = 0; t != s; t = (t - s) & s) {  // t is a proper subset of s
            if (__builtin_popcount(s ^ t) == 1) {
                chmin(dp[s], dp[t] + 1);
            } else {
                int acc = 0;
                REP (x, MAX_A + 1) if ((s ^ t) & (1 << x)) {
                    acc ^= x;
                }
                if (acc == 0) {
                    chmin(dp[s], dp[t] + __builtin_popcount(s ^ t) - 1);
                }
            }
        }
    }
    return removed + dp[cnt];
}

int main() {
    // input
    int n; cin >> n;
    vector<int> x(n - 1), y(n - 1), a(n - 1);
    REP (i, n - 1) {
        cin >> x[i] >> y[i] >> a[i];
    }

    // solve
    int answer = solve(n, x, y, a);

    // output
    cout << answer << endl;
    return 0;
}