首页 > 小红的树上删边
开通博客写题解
头像 此在Dasein
发表于 2025-12-27 02:01:40
该问题本质上是一个树的分解（Tree Partitioning）问题。我们需要将一棵包含 个节点的树分解成尽可能多的连通块（Connected Components），且需满足一个硬性约束条件：每个连通块的节点数必须为偶数。 关键约束： 总节点数奇偶性： 如果一棵树的总节点数 是奇数，那么无论 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 Jakeap
发表于 2025-12-27 12:40:53
解答：思路：首先这题是一个树的分解问题，题目明确给了分解的要求就是分解后连通部分的结点数目是偶数。这句可以得到特殊情况，如果总结点数目是奇数，那么直接输出-1即可，如果是偶数继续往下分析。题目还要求删除边的个数最多，那么问题转换为删除若干条边后使得连通部分结点个数是偶数且尽可能最小，最小不就是2！这 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Coldmou4
发表于 2024-05-14 23:01:03
根据题意显然可得，若从一个节点断掉一条边，以这个节点为根节点的子树大小是偶数的话，是不会影响剩余节点的奇偶性的，所以断边等于没断，那么断边其实是不需要我们真正进行操作的 既然切断一棵大小是偶数的子树不会影响剩下的奇偶性，那么我们就进行贪心即可，尽可能多的去切断一棵大小是偶数的子树，所以只要进行一次d 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 quchen666
发表于 2025-12-27 00:47:57
#include <bits/stdc++.h> using namespace std; const int N = 3e5+10; vector<int>e[N]; int sz[N]; int n; int ans = 0; void dfs(int u,int fa 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 IA3000
发表于 2025-12-27 01:20:38
注意到随便选定一个点为根，对于非根节点 u 来说，它的连向父亲的边能够删，当且仅当该点为根的子树大小为偶数。因为子树中不管已经删除多少次边了，删除连向父亲的后该点所在的连通块的大小（每次减偶数）的奇偶性始终不变（与原来子树大小相同） #include <bits/stdc++.h> us 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 YunBaichuan
发表于 2025-12-27 10:24:30
思路：首先要想到一个特判，那就是当节点n的个数为奇数时，必然不满足条件中的全偶数划分。然后就是贪心进行划分，什么意思？打个比方来说，我在4的时候进行划分，不如在2的时候就进行划分，这样就可以多一次划分，更优 所以说，我们可以统计子树大小，一旦遇到偶数就进行划分，这可以用递归dfs来做。具体来说，当我 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 smartiphone
发表于 2025-12-27 13:19:49
#include <vector> #pragma GCC optimize(2) #include<bits/stdc++.h> #define endl '\n' #define INF 0x7fffffff #define _ << ' ' << 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 olone
发表于 2025-12-27 21:25:40
#include<iostream> using namespace std; const int N=1e5+5; int n; int head[N],cnt; int siz[N]; int ans; struct node { int next; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”