AT3913 XOR Tree

需要略带转换的状压 dp

---

题意

给定一棵 $n$ 个节点的树，每条边有边权 $a$ ，一次操作可以将节点 $u$ 到 $v$ 的路径上的边的边权异或上 $x$ ,问至少需要多少次操作可以将所有边的边权变为 $0$ 。
其中 $1 \leq n \leq 10^5, 0 \leq a_i, x \leq 15$ 。

思路

对于一条路径上的操作不好维护，可以考虑类似差分的想法，将对链的操作转换一下。
对于树上的一条路径，路径中除了两端的点之外，其余的所有点都恰有两条边的边权被异或上 $x$ ，若考虑定义一个点的点权为所有与它相邻的边的边权的异或和，那么一次操作可以转换为将路径两端的点的点权异或上 $x$ （中间点的操作都被抵消了）。
计算出每个点的点权后，相等的权值可以互相抵消，最后剩下的一定是 $1$ 到 $15$ 中每个数最多一个，问题转化为一次将两个数异或上 $x$ ，用最少的操作将所有剩下的数都变为 $0$ ，由于值域只有 $15$ ，状压 DP 即可。
预处理加DP的总复杂度为 $O(n + 2^{15})$ 。

代码

代码实现很短。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

constexpr int INF=0x3f3f3f3f;
constexpr int N=1e5+5;

int n;
int a[N];
int num[16];
int ans;
int dp[1<<16];

int search(int mask){
    if(dp[mask]!=INF) return dp[mask];
    for(int i=1;i<16;i++) if((mask>>i)&1)
        for(int j=i+1;j<16;j++) if((mask>>j)&1){
            if((mask>>(i^j))&1) dp[mask]=min(dp[mask],search(mask^(1<<i)^(1<<j)^(1<<(i^j)))+2);
            else dp[mask]=min(dp[mask],search(mask^(1<<i)^(1<<j)^(1<<(i^j)))+1);
        }
    return dp[mask];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>n;
    for(int i=0,x,y,z;i<n-1;i++){
        cin>>x>>y>>z;
        a[x]^=z;
        a[y]^=z;
    }
    for(int i=0;i<n;i++) num[a[i]]++;
    for(int i=1;i<16;i++) ans+=num[i]/2,num[i]%=2;
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    int mask=0;
    for(int i=1;i<16;i++) if(num[i]) mask|=(1<<i);
    cout<<ans+search(mask);

    return true&&false;
}