题解 AT3913 【XOR Tree】

题意

给你一颗无根树，每条边有权值 w_i ,可以选择一条简单路径，将路径上的边权 xor 一个值。最后使所有边全部为 0 。求最小次数 。 QwQ

分析

• 如果我们直接对边权操作的话，不仅状态难以表示，而且贪心也可以很容易找到反例。这时候我们就需要改变一下思路。

• 如果只是简单的把到父亲的边映射到该节点，那么我们可以通过 xor 的交换律证明： root 到 a,b 之间的路径异或一个值是等价于 a,b 的简单路径异或这个值的。

• 通过上面的转换我们可以想到将所有链接这个点的所有边的异或和，作为这个点的点值。

• 我们先猜一个结论 \sum_{i=node}val_i = 0 时，\sum_{i=edge} val_i = 0 。如何证明，写在后文。

• 如果结论成立那么，我们进行一次操作只会影响两个节点。所以进行一次操作最多也只可以试两个点权值变为 0 。而且 a \ xor \ c , b\ xor\ c 一定是劣于 a \ xor \ a , b\ xor\ a 的。因此每一次最少消去 1 个点，最多 2 个 。

• 因为以上性质，我们可以先贪心的选取权值一样的删去，最后再考虑留下的如何删去。 0 \le a_i\le 15 这使我们可以考虑状压 dp 。因为只有最后异或和为 0 的集合才可能删完（每次修改两个点）。所以我们可以枚举子集。然后转移就行了。

  dp[S] = \min(dp[S \ xor\ S^{'}]+dp[S^{'}]) (xorsum[S^{'}]=0)

• 因为在算点权时每条边被算了两次，又因为 x \ xor \ x = 0 ，所以一定是有解的。

证明

• 必要性证明： 因为所有边权全部为 0 ，所以点权也一定为 0 。

• 充分性证明 这是一个节点个数为 n 的树。所以对于叶子节点一定度数为 1 。因为点权为 0 ，所以链接父亲的边的权值一定为 0 。 这时候这条边已经不会影响父亲的点权了。所以按此归纳:

  \sum_{i=node}val_i = 0\Rightarrow \sum_{i=edge} val_i = 0

代码

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)){ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x;
}
const int N = 1e6;
int n,sum[1<<17],val[N],num[N],S,dp[1<<17];
int main()
{
    n = read();
    for(int i = 1;i < n;i++)
    {
        int a = read()+1,b = read()+1,w = read();
        val[a] ^= w;val[b] ^= w;
    }
    for(int i = 1;i <= n;i++) num[val[i]]++;
    int ans = 0;
    for(int i = 1;i < 16;i++)
    ans += num[i]/2,S |= ((num[i]&1)<<i-1);
    for(int i = 1;i < 1<<15;i++)
    {
        for(int j = 1;j < 16;j++)
        {
            sum[i] ^= j * ((i>>(j-1))&1);
            dp[i] += (i>>(j-1))&1;
        }
        dp[i]--;
    }
    dp[0] = 0;
    for(int i = 1;i < 1<<15;i++)
    {
        if(sum[i]) continue;
        for(int j = i;j;j=(j-1)&i)
        {
            if(sum[j]) continue;
            dp[i] = min(dp[i],dp[i^j]+dp[j]);
        }
    }
    cout<<ans+dp[S]<<endl;
    return 0;
}