[cf] 746 div2 C. Bakry and Partitioning

前言

T a g : Tag: Tag:异或 树 dfs *1700 传送门 :

题意 : 给定一棵树,你可以删除最少 1 1 1,对多 k − 1 k-1 k−1 条边,询问是否可以使得删除边之后,每个连通分量中的异或和相等

思路 :

考虑删除一条边( k = 2 k=2 k=2)的情况

a x ⊕ ( a 1 ⊕ a 2 . . . . a n ) = 0 a_x \oplus(a_1\oplus a_2....a_n)=0 ax​⊕(a1​⊕a2​....an​)=0

也就是 a 1 ⊕ a 2 ⊕ a 3 . . . . . a n = s u m = 0 a_1\oplus a_2\oplus a_3.....a_n = sum= 0 a1​⊕a2​⊕a3​.....an​=sum=0

如果 s u m ! = 0 sum!=0 sum!=0,那么因为两个连通块需要异或和相同 b ⊕ b = s u m = 0 b\oplus b=sum=0 b⊕b=sum=0,但是 s u m ! = 0 sum!=0 sum!=0

因此 k = 2 k=2 k=2的时候,只有 s u m = 0 sum=0 sum=0是合法的

然后我们考虑删除多条边的情况 k > = 3 k>=3 k>=3

首先这里抛出一个贪心的思路 : 在异或考虑最优的情况下 : 如果选择 三个商品异或相同 并且 五个商品异或也相同,那么我们考虑选择三个商品的最优 up:电音不抖腿

因此我们可以 d f s dfs dfs每一个子树,然后计算其异或和,当且仅当第一次 t o t a l = = s u m total==sum total==sum的时候,我们就进行一次分割

同时又因为 a ⊕ a ⊕ a = a a\oplus a \oplus a =a a⊕a⊕a=a因此最少都需要两个割点,所以最后判断分割的点是否是两个以上即可

code :

vector g[N];
int n,k;
int w[N];
int cnt;

int total;

int dfs(int u,int fa){
	int val =  w[u];
	
	for(auto x :  g[u]){
		if(x == fa)continue;
		
		int tmp = dfs(x,u);
		if(tmp == total) cnt ++;
		else val^=tmp;
		
	}
	return val;
	
}
void solve(){
	cin>>n>>k;
	total = 0 ;
	cnt = 0;
	
	
	for(int i = 1;iw[i];
		total^=w[i];
	}
	
	for(int i=1;i>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	
	if(total == 0){
		cout