首页 > 小美的树上染色
开通博客写题解
头像 牛客664857134号
发表于 2023-08-22 10:47:48
D题解 | #小美的树上染色# 经典的树形DP 1、以节点1为根节点建树（任何一个节点为根节点都行）； 2、dp[i][0] 表示以节点i为子树根节点时，节点i没有被染色时整个i节点子树可以被染色的最多节点数量；同样 dp[i][1] 表示以节点i为子树根节点时，节点i被染色时整个i节点子树可以被染 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 Coldmou4
发表于 2023-08-21 11:41:23
D题 可以当成二分图最大匹配问题来做 这里用的是匈牙利算法 (但是没有dp快 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n,match[N],w[N]; vector<int& 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Tswatery
发表于 2023-08-21 20:33:03
暴力做 D 如果一个节点有多个孩子，它最多只能和一个孩子进行染色，因此暴力搜索即可哪些节点能一起染色即可。 #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 1 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”