题解 AT3913 【XOR Tree】

· · 题解

看起来是个NlogN其实是个假的复杂度

知道为什么值域只有15这么小吗，因为要状压……

题意简述:给定一棵树，边上有边权,你可以重复以下操作若干次，将u,v间路径上的所有边异或上同一个数x，求最小的操作次数，使得操作后所有边的边权都为0

那么我们发现直接对边权做手脚的话这题就有点不可做了

因为我们每一次操作都会修改O(n)条边的边权

所以我们考虑搞点奇技淫巧让这个边权变成点权

那么我们令每个点的点权为它周围一圈边(意会就好，这个概念不难理解)边权的异或和

现在让我们看看当我们给u,v上路经的边都异或一个权值x的时候，点权会发生什么变化

我们发现只有u,v的点权异或了一个x，其余的点的点权都不动……，因为如果这个点不是路径端点的话，左边的边被异或了一个x的同时右边的点也被异或上了一个x 这样的话这个点的点权是不动的……

现在的问题变成了给你一堆数字，每次可以挑两个数并让他们异或上同一个数字，求最小的异或次数使得所有数字变为0的操作次数

当然我们可以贪心了，如果存在两个相同的数字对，那么我们可以通过一次操作将这一对数字消去

那么我们重复这样的流程

最后最多剩下16个值互不相同的数字

那么这个时候我们不能贪心了，接下来该怎么做呢？

发现数字个数非常少，因此我们可以状压dp

那么具体来讲我们会发现一个这样的性质

一个数字的集合有解(也就是说可以用取两个数字异或上同一个数字将这个集合里的所有数字变成0)当且当这个数字集合的异或和为0

正确性显然，因为每次操作均不改变这个集合的异或和，所以如果一开始不是0的话是无论如何都消不成一个全零集合的

因此我们可以设dp_{s}表示将s这个集合全部变成0的最小操作次数

如果s的异或和不为0的话直接不计算这个东西的dp值，因为它不合法

否则的话我们认为dp_{s}有一个下界是这个集合s的size-1,(就是暴力的一个一个消成0)

那么转移呢？

我们发现可以如果我们能将这个集合拆成两个互不相交的子集，并且，我们拆出来的这两个子集的异或和都是0的话，我们就可以至少减少一次操作

所以转移就是枚举每个集合的子集然后进行转移，取一下min就好了

复杂度

\sum_{i=1}^{16}C_{16}^{i}2^i=(1+2)^{16}=3^{16}

总复杂度O(3^{16}+N)

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=2*1e5+10;
int w[N];int d[N];int cnt[20];int res;int n;int st;bool book[N];int sxr[N]; 
int main()
{
    scanf("%d",&n);
    for(int i=1,u,v,va;i<n;i++){scanf("%d%d%d",&u,&v,&va);w[u]^=va;w[v]^=va;}
    for(int i=0;i<n;i++){cnt[w[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]-=1;//预处理每个dp值的下界 
    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]);
    }printf("%d",res+d[st]);return 0;
}