「APC001F」XOR Tree

发表于 分类于

$Link$

给定一棵 $n$ 个点的树，边上有边权 $a_i$。

每次操作可以把一条简单路径上所有边的边权异或上一个数，求把所有边的权值都变成 $0$ 的最小操作次数。

$2\le n\le10^5,0\le a_i\le15$。

不变量好哇。

把路径画出来，再由异或的性质可以发现，如果我们令点权为连接它的所有边的边权的异或和，操作就相当于选择两个点把它们一起异或上这个值。注意到点权不超过 $15$。

最后的要求等价于点权全部消成 $0$。充分性显然，必要性考虑从叶子往上推也容易得到。

先把点权为 $0$ 的丢掉。显然，有解当且仅当剩下的数的个数是偶数。每次操作我们至少能消掉一个数，这是操作上界。而减小操作数的方法就是每次消掉两个数，也即找到两个相同的数。因此如果有相同的数，优先消掉，剩下最多 $15$ 个数。

剩下的数显然是通过某种消去顺序，使得有数相同来尽量减少操作数。并且不可能操作一次却没有消去任何数，这样答案不会更优。 那么直接暴力 $dp$ 即可。

时间复杂度 $O(3^{15})$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 1e5;

int n;
int val[N + 1], sum[16], state;
int can[1 << 15], f[1 << 15];
int ans;

int main()
{
    n = read();
    for (int i = 1; i < n; i++) {
        int u = read() + 1, v = read() + 1, w = read();
        val[u] ^= w;
        val[v] ^= w;
    }
    for (int i = 1; i <= n; i++)
        sum[val[i]]++;

    for (int i = 1; i < 16; i++) {
        ans += sum[i] >> 1;
        sum[i] &= 1;
        state |= sum[i] << (i - 1);
    }
    for (int S = 0; S < 1 << 15; S++) {
        int sum = 0, tot = 0;
        for (int i = 1; i <= 15; i++) {
            if (S & (1 << (i - 1))) {
                sum ^= i;
                tot++;
            }
        }
        if (!sum)
            can[S] = 1;
        f[S] = tot - 1;
    }
    f[0] = 0;
    for (int S = 0; S < 1 << 15; S++) {
        for (int T = (S - 1) & S; T; T = (T - 1) & S)
            if (can[T])
                f[S] = min(f[S], f[T] + f[S ^ T]);
    }

    printf("%d\n", f[state] + ans);
    return 0;
}