淘先锋技术网

首页 1 2 3 4 5 6 7

题目链接:https://atcoder.jp/contests/apc001/tasks/apc001_f

AT3913-XOR Tree

压状DP,位运算
题目大意为给定一棵树,每条边有边权,一次操作可以将节点 u u u v v v 路径上的边的边权异或上 x x x ,问至少需要多少次操作可以将所有边的边权变为 0 0 0
对于一次操作,若要修改一整条路径,显然不易维护边权,因为只涉及修改操作,这个地方可以参考差分的思路。若是对于链上的情况,可以对数列做一次异或差分,那么单次的修改就转换成了修改两个端点值。
那么对于在树上的情况,也考虑将修改转换为点权的修改。考虑到修改一条路径时,除了两个端点外,其余点的边都被修改了两次,根据异或的自反性,可以定义一个点的点权为所有与它相连的边的边权的异或和,那么修改一次路径,对于路径中的点,它的权值被异或了两次,权值不变,只有端点的权值会改变,那么修改一条路径的操作就可以转换为修改两个端点的权值。
那么计算出每个点的权值后,相等的权值可以直接相互抵消,因为 0 ≤ a i ≤ 15 0≤a_i≤15 0ai15 ,最后剩下的数一定是 1 1 1 15 15 15 至多一个,那么问题即是最小的操作数将剩余的数变为 0 0 0 ,因为题目保证有解,剩下来数的异或和一定为 0 0 0 ,我们一定可以在 n − 1 n-1 n1 ,步操作内完成,但考虑若剩下来的数可以划分成多个异或和为 0 0 0 的小集合,对于每个集合我们可以减少一次操作,所以这个地方的操作数不能简单地计算为 n − 1 n-1 n1 ,考虑 a i a_i ai 的范围,可以用一个状压DP来处理操作数,具体实现见代码。

#include<bits/stdc++.h>
#define next next_
#define last last_
#define y1 yy
#define hash hash_
#define complex complex_
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

ll mod=1e9+7,mod2=1e9+9;
const ull base=101;
const double pi=acos(-1.0);
int _;

int n,a[100010],num[22];
int u[200010],v[200010],w[200010],next[200010],first[100010];
int f[67010];

int search(int s){
	if(f[s]!=1061109567) return f[s];
	for(int i=1;i<16;i++)
		foR(int j=i+1;j<16;j++)
			if(((s>>i)&1)&&((s>>j)&1)){//若数字i,j都存在,同时异或上一个i
				if((s>>(i^j))&1) f[s]=min(f[s],search(s^(1<<i)^(1<<j)^(1<<(i^j)))+2);//异或后结果为0和i^j,若i^j原本存在,则再进行一次操作将两个相同的i^j消去,操作数+2
				else f[s]=min(f[s],search(s^(1<<i)^(1<<j)^(1<<(i^j)))+1);//若i^j原本不存在,则继续搜索,操作数+1
			}
	return f[s];
}

void work(){
	memset(first,-1,sizeof(first));
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		scanf("%d%d%d",&u[2*i],&v[2*i],&w[2*i]);
		u[2*i]++;v[2*i]++;
		u[2*i+1]=v[2*i];v[2*i+1]=u[2*i];w[2*i+1]=w[2*i];
		next[2*i]=first[u[2*i]];
		first[u[2*i]]=2*i;
		next[2*i+1]=first[u[2*i+1]];
		first[u[2*i+1]]=2*i+1;
	}
	foR(int i=1;i<=n;i++){
		int k=first[i];
		while(k!=-1){
			a[i]^=w[k];
			k=next[k];
		}
	}
	int sum=0;
	foR(int i=1;i<=n;i++) num[a[i]]++;
	for(int i=1;i<16;i++) sum+=num[i]/2,num[i]%=2;
	memset(f,127/2,sizeof(f));
	f[0]=0;
	int ans=0;
	for(int i=1;i<16;i++) iF(num[i]) ans|=(1<<i);//ans每一位代表该数字存不存在
	printf("%d",sum+search(ans));
}

int main(){
	_=1;
	// cin>>_;
	// scanf("%d",&_);
	while(_--){
		work();
		// if(_) printf("\n");
	}
	return 0;
}