AT3913 XOR Tree 题解

题意：给你一棵有 \(N\) 个节点的树，节点编号从 \(0\) 到 \(N-1\) ，树边编号从 \(1\) 到 \(N-1\) 。第 \(i\) 条边连接节点 \(x_i\) 和 \(y_i\) ，其权值为 \(a_i\)。

你可以对树执行任意次操作，每次操作选取一条链和一个非负整数 \(x\)，将链上的边的权值与 \(x\) 异或成为该边的新权值。

问最少需要多少次操作，使得所有边的权值都为 \(0\) 。

\(2\le N \le10^5,0\le x_i,y_i \le N-1,0\le a_i \le 15\)

首先可以想到：

边权不好处理，将其转化为点权

不过如果直接转化为点权似乎还是不好弄 ~~q779想到这就没了~~

我们知道异或有自反性 \((p\oplus q \oplus p = q )\) 等性质

则考虑将点权定义为 \(\text{val}(u) = \bigoplus\limits_{v_i \in V \land (u,v_i) \in E}w(u,v_i)\)

也就是和每个结点直接相邻的边的边权的异或和

此时我们就将边权映射到了点权上（注意本题可以看作一棵无向无根树）

路径 \(u-v\) 的修改转化为了 \(u,v\) 两个点的修改

因为点权是异或和

所以同时修改路径上某个非端点结点所连的两条边，异或和不变（自反性）

首先，我们来证明几个结论

命题1 ：当且仅当 \(\sum_{u_i\in V} \text{val}(u_i)=0\) 时，\(\sum_{l_i\in E} w(l_i) = 0\)。

证明：

必要性证明：显然当边权和为 \(0\) 时，点权和也为 \(0\) 。
充分性证明：设树上的结点数为 \(n\) ，若叶子结点 \(u\) 的点权为 \(0\)

则与其相连的边的边权也为 \(0\) ，因此这条边不会影响到 \(u\) 的父结点，归纳可得

\[ \sum_{u_i\in V} \text{val}(u_i)=0 \Rightarrow \sum_{l_i\in E} w(l_i) = 0 \]

命题2：一个数字集合通过不断取两个数字并异或上同一个数有解，当且仅当这个数字集合异或和为 \(0\) 。

证明：显然，因为每次修改不会改变该集合的异或和。

命题3：\(\bigoplus\limits_{u_i\in V} \text{val}(u_i) = 0\) 。

证明：显然，每条边都有两个端点，根据自反性可得。

这样，我们就可以贪心地选择两个点权相同的结点消掉了

可是如果没有没有点权相同的结点了怎么办呢？

可以发现，此时最多有 \(16\) 个互不相同的数字，而 \(0\) 不用考虑，因此最多只有 \(15\) 个数字

考虑状压dp

令 \(dp_s\) 为将数字集合 \(s\) 全部变为 \(0\) 的最小操作数

显然至多要 \(|s|-1\) 次操作（也就是原图中一条条边消）

直接去搞是有后效性的，所以考虑如何转移

我们可以枚举 \(s\) 的一个子集 \(k\) ，则有 \(dp_s = \min(dp_s,dp_k+dp_{s/k})\)

复杂度怎么样呢？ \[ \begin{aligned} O\left( \sum\limits_{i=1}^{15}\operatorname{C}_{15}^i2^i + n\right) &= O\left((1+2)^{15}-1 + n\right) \\ &= O(3^{15}+n) \\\\ &= O(n) \end{aligned} \] 代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)
int n,val[N],d[N],cnt[25],res,st,sxr[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1,u,v,w; i<n; i++)
        cin >> u >> v >> w,val[u]^=w,val[v]^=w;
    for(int i=0; i<n; i++) ++cnt[val[i]];
    for(int i=1; i<=15; i++) res+=cnt[i]/2,st|=(cnt[i]&1)<<(i-1);
    for(int i=1; i<(1<<15); i++) d[i]=d[i>>1]+(i&1);
    for(int i=1; i<(1<<15); i++)--d[i];
    for(int i=1; i<(1<<15); i++)
        for(int j=0; j<15; j++)if((i>>j)&1)sxr[i]^=(j+1);
    for(int i=1; i<(1<<15); i++)
    {
        if(sxr[i]!=0)continue;
        for(int k=(i-1)&i; k; k=(k-1)&i)
            if(sxr[k]==0)d[i]=min(d[i],d[k]+d[i^k]);
    }
    cout << res+d[st] << endl;
    return 0;
}