codeforces1592:C. Bakry and Partitioning

codeforces1592:C. Bakry and Partitioning

题目大意
题目给出了一颗有 n n n 个顶点的树，每个点都有一个权值 a i a_i ai​ ,求可否满足去掉最少一条边，最多 k k k 条边后，剩下的连通块的异或和相等。
题解
这道题，我们可以分两种情况讨论：首先，如果所有点的异或和 x o r s u m xorsum xorsum 是 0 0 0 那么，一定可以任意将这颗树分成两个连通块，此时这两个连通块的异或值是相等的。
其次，如果 x o r s u m xorsum xorsum 不为 0 0 0 那么我们肯定会将整棵树分成奇数块连通块。假设分成 m m m 块连通块 ( m m m 为奇数 )： B 1 , B 2 , B 3 , . . . . , B m B_1 ,B_2 ,B_3,....,B_m B1​,B2​,B3​,....,Bm​ 由于每一块的异或值都是一样的，那么就存在：
B 1 x o r B 2 x o r B 3 x o r B m − 2 = B m − 1 = B m = B 1 B_1quad xor quad B_2quad xorquad B_3 quad xor quad B_{m-2}= B_{m-1}=B_m=B_1 B1​xorB2​xorB3​xorBm−2​=Bm−1​=Bm​=B1​
至此，我们只要找到三个异或和相等的连通块就可以成立，并且每个连通块的异或和就是总的异或和。
我们可以通过dfs去寻找子树（包含这个点）异或和等于 x o r s u m xorsum xorsum 的点，将它从树上去掉，然后在剩下异或和为 0 0 0 的树中找到子树异或和为 x o r s u m xorsum xorsum 的点。 都找到说明满足条件。

#include
using namespace std;
int n,k;
const int N=1e5+10;
int xsum[N],in[N],out[N],a[N],f[N];
std::vectorvt[N];
int dfn;
int dfs(int u,int fa)
{
	in[u]=++dfn;
	f[u]=fa;int sum=a[u];
	for(auto v:vt[u])
	{
		if(v==fa)continue;
		sum^=dfs(v,u);
	}
	xsum[u]=sum;
	out[u]=++dfn;
	return sum;
}
void dfst(int u,int &p1,int &ck)
{
	if(xsum[u]==0||xsum[u]==ck)
	{
		p1=u;
	}
	for(auto v:vt[u])
	{
		if(v==f[u])continue;
		
		dfst(v,p1,ck);
	}
}
int main()
{
	int t;cin>>t;
	while(t--)
	{
		int sum=0;dfn=0;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;++i)vt[i].clear();
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&a[i]);
			sum^=a[i];
		}
		for(int i=1;iout[p1])&&xsum[i]==sum)
			{
				if(k>2)ans=1;
			}
			if(xsum[p1]==0&&(in[i]>in[p1]&&in[i]2)ans=1;
			}
		}
		if(ans)
		{
			printf("YESn");
		}
		else
		{
			printf("NOn");
		}
	}
}