题面

给定 $n$ 个节点的树，每条边有权值 $val_i\in[1,15]$ 每次操作可以选一条路径异或上一个数，最小化操作次数

解题思路

转边权为点权，然后状压DP

分析

首先，如果边权就有点复杂了，考虑如何把边权转化为点权，不难发现，对于一条路径中出了两端的点，每个点都有两两条边与之相连，那么就可以将边权转换为点权，每个点的权值即为所有与之相连的边权值的异或和，这样的话，对一条路径进行操作就变成了对两个点进行操作。又因为所有权值的大小不超过 $15$，范围很小，我们只要开个桶记录一下，权值相同的两两做一次操作即可，这样剩下来不为 $0$ 的点的数量就不超过 $15$ 个了，使用各种奇淫巧技都可以写过去（当然是据说

用状压 $DP$ 可以解决，$f[i]$ 表示状态为 $i$ 时的最小次数，当然 $i$ 需要是一个异或可以为 $0$ 的状态，每个 $i$ 可以从子集转移过来

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100007
using namespace std;
const int T=1<<15;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,t,d[N],sum[19],f[T+3],st,ans,p[T+3];
int main()
{
    rint i,j,x,y,val;n=read();
    for(i=1;i<n;i++)
        x=read(),y=read(),val=read(),d[x]^=val,d[y]^=val;
    for(i=0;i<n;i++) ++sum[d[i]];
    for(i=1;i<16;i++) ans+=sum[i]>>1,st|=(sum[i]&1)<<(i-1);//st表示最终状态
    for(i=1;i<T;i++) f[i]=f[i>>1]+(i&1);//每个状态有几个1
    for(i=1;i<T;i++) --f[i];//f[i]表示每种状态最少做几次即可全部为0,最劣情况明显是1的个数-1
    for(i=0;i<T;i++)
        for(j=0;j<15;j++)
            if((i>>j)&1) p[i]^=(j+1);//每个状态的异或和
    for(i=0;i<T;i++) {
        if(p[i]) continue;//就是异或和能不能为0
        for(j=(i-1)&i;j;j=(j-1)&i)//枚举子集
            if(!p[j]) f[i]=min(f[i],f[j]+f[i^j]);//从异或为0的子集转移过来
    }printf("%d",ans+f[st]);
    return 0;
}

devil.