AT3913 XOR Tree 题解

ATcoder
Luogu

Description.

给定一棵树,边带权,每次选择一条链并对上面所有边 \(\oplus\) 上一个任意值。
询问至少几次可以使所有边权变为 \(0\)。

Solution.

没想到那个巧妙的构造。

构造点权为它周围所有边权的 \(\oplus\)。
这样每次修改相当于选择两个不同的点 \(x,y\) 和一个权值 \(v\) 并 \(a_x\leftarrow a_x\oplus v,a_y\leftarrow a_y\oplus v\)。
因为操作次数最小,所以选择相同的两个数肯定不能最小化,所以可以把不同去掉。
然后贪心地考虑,如果有两个数相同,花一步消掉他们一定最优,剩下的数不会超过 \(a_i(\le 15)\) 个。
直接状压即可。
复杂度 \(O(2^{a_i}+n)\)

Coding.

别点击了,下面这种垃圾有谁来看
//是啊……你就是那只鬼了……所以被你碰到以后,就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(f) x=-x;
}/*}}}*/
int n,a[100005],dp[100005],xr[100005],rs=0,tn[20];
int main()
{
	read(n);for(int i=1,x,y,w;i<n;i++) read(x),read(y),read(w),a[x]^=w,a[y]^=w;
	for(int i=0;i<n;i++) tn[a[i]]++;
	for(int i=1;i<=15;i++) rs+=tn[i]>>1,tn[i]&=1;
	int S=0;for(int i=1;i<=15;i++) S=S|(tn[i]<<(i-1));
	dp[1]=0;for(int i=2;i<(1<<15);i++) dp[i]=dp[i>>1]+(i&1);
	for(int i=1;i<(1<<15);i++) for(int j=0;j<15;j++) if((i>>j)&1) xr[i]^=j+1;
	for(int i=1;i<(1<<15);i++) if(!xr[i])
		for(int j=(i-1)&i;j;j=(j-1)&i) if(!xr[j]) dp[i]=min(dp[i],dp[j]+dp[i^j]);
	return printf("%d\n",rs+dp[S]),0;
}
上一篇:CF1483E Vabank 题解


下一篇:算法|堆排序