【Codeforces |
您所在的位置：网站首页 › codeforces和leetcode › 【Codeforces |
|
原题链接：Bakry and Partitioning 题意给你一棵共n个节点的树，每个节点有对应的值，要求删除1~(k-1)条边使得所有连通块的异或和相同。 分析对于树上异或和问题，通用做法是先处理出每个节点与其子树所有节点的异或和，一遍dfs便可获得。 一棵树删除一条边后，便会产生两个连通块，也可称为子树，【原根节点所在子树的异或和】需要异或上 【另一子树的异或和】，因为一个数连续异或相同的数两次还是原来的数。 由此可见，当只删除一条边时，要保证两个新的连通块异或和相同，当且仅当【原树异或和】等于0，因为0异或上任何数都等于那个数，这个情况下要删除的边是任意的。 接下来讨论当【原树异或和】不是0的情况： 这种情况下要保证所有连通块的异或和相同，那么【原树异或和】必定是答案，可以手动推敲一下。那么【根节点所在连通块的异或和】可以连续异或【原树异或和】偶数次，为了简化问题我们设为2次。 如果有两棵子树的异或和等于【原树异或和】，则可以直接删除连接这两棵子树的边。 另一种情况是存在子树异或和为0，且该子树也需要存在异或和为【原树异或和】的子树。 总结符合条件的情况： 1、【原树异或和】等于0； 2、k >= 3，存在两棵子树的异或和等于【原树异或和】； 3、k >= 3，存在子树异或和为0，且该子树也需要存在异或和为【原树异或和】的子树。 代码 #include #include using namespace std; const int N = 4e5 + 7; int h[N], ne[N], e[N], idx, val[N], ok; void add(int u, int v) { e[++idx] = v, ne[idx] = h[u], h[u] = idx; } void dfs(int u, int fa) { for (int i = h[u]; i; i = ne[i]) { int v = e[i]; if (v == fa)continue; dfs(v, u); val[u] ^= val[v]; } } bool dfs2(int u, int fa) { if (ok)return true; int cnt = 0; for (int i = h[u]; i; i = ne[i]) { int v = e[i]; if (v == fa)continue; cnt += dfs2(v, u); } if ((cnt && val[u] == 0) || cnt >= 2)ok = 1; return cnt || (val[u] == val[1]); } void solve() { idx = ok = 0; int n, m; scanf("%d%d", &n, &m); for (int i = 1; i int t; cin >> t; while (t--)solve(); return 0; } |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |