Codeforces1592CBakryandPartitioning(思维)

给定一棵有$n$个节点的树, 第$i$个节点有权值wiw_iwi​.

问你能否把这棵树分成$[2,k]$个部分, 使得每部分中所有节点的异或和相同.

解题思路

思维 (至暗时刻, 我比赛时在干什么啊!!)

首先考虑到如果整棵树上的所有节点, 异或和$sum\&＃61;\&＃61;0$, 那么我们一定可以把整棵树拆成两部分, 满足题意.

我们可以选择任一叶子结点$x$, 然后删除该节点到其父亲的边, 这样两部分的结点异或和一定均为wxw_xwx​

如果整棵树上的所有节点异或和$sum/\&＃61;0$, 那么我们一定要把整棵树拆成奇数(≥3)个部分, 使得每部分的异或和为$sum$.

至于为什么每部分的异或和一定为$sum$.

我们不妨设整棵树被分成了$3$部分, 每部分的异或和为$x$.

则有: $x\oplus x\oplus x\&＃61;\&＃61;sum$, 由于$x\oplus x\&＃61;\&＃61;0$, 则$x\&＃61;\&＃61;sum$.

如果要把整棵树分成奇数(≥3)个部分, 那么分成$3$个部分一定是最优的.

当我们把整棵树拆分成$num$($num$为奇数)个部分, 由于原先是树是连通的, 那么拆分后, 每个部分也必然会有对应原先和它连通的部分. 因此我们可以不断合并$3$个连通的部分, 使得$num\&＃61;3$.

例如题中样例, 有$5$个节点, 每个节点的权值都是3. Note中给出了分成5个部分的答案, 其实也可以分成3个部分.

接下来考虑如何拆分.

我们应该求出这棵树最多能拆分成多少个部分, 使得每部分的异或和为$sum$. 那么在进行拆分时, 我们每次拆分出的一定是一棵子树, 一旦某棵最小的子树满足条件, 我们把这棵子树删除, 继续拆分即可.

如果拆分出的不是一颗子树, 那么当前节点的子节点不再和其他节点连通, 会导致该部分的异或和不为$sum$.

我们可以通过dfs的方式来得到最大拆分数量.

AC代码

#include
#define rep(i, n) for (int i &＃61; 1; i <&＃61; (n); &＃43;&＃43;i)
using namespace std;
typedef long long ll;
const int N &＃61; 1E5 &＃43; 10;
int w[N];
vector<int> edge[N];int all &＃61; 0; // 统计最大能拆分出多少个部分
int dfs(int x, int fa, const int target) { // 返回当前子树异或和int now &＃61; w[x]; // 统计当前子树异或和for (auto& to : edge[x]) {if (to &＃61;&＃61; fa) continue;now ^&＃61; dfs(to, x, target);}if (now &＃61;&＃61; target) { //该子树满足条件, 拆分部分&＃43;&＃43;, 并删除该子树all&＃43;&＃43;;return 0;}return now;
}
int main()
{int t; cin >> t;while (t--) {int n, m; scanf("%d %d", &n, &m);int sum &＃61; 0;rep(i, n) scanf("%d", &w[i]), edge[i].clear(), sum ^&＃61; w[i];rep(i, n - 1) {int a, b; scanf("%d %d", &a, &b);edge[a].push_back(b);edge[b].push_back(a);}if (!sum) {puts("YES");continue;}all &＃61; 0;dfs(1, 0, sum);if (all >&＃61; 3 and m >&＃61; 3) puts("YES");else puts("NO");}return 0;
}


END