【图论 DFS 换根法】3772. 子图的最大得分|2235
本文涉及知识点
C++图论 换根法
LeetCode3772. 子图的最大得分
给你一个 无向树 ，它包含 n 个节点，编号从 0 到 n - 1。树由一个长度为 n - 1 的二维整数数组 edges 描述，其中 edges[i] = [ai, bi] 表示在节点 ai 和节点 bi 之间有一条边。
另给你一个长度为 n 的整数数组 good，其中 good[i] 为 1 表示第 i 个节点是好节点，为 0 表示它是坏节点。
定义 子图 的 得分 为子图中好节点的数量减去坏节点的数量。
对于每个节点 i，找到包含节点 i 的所有 连通子图 中可能的最大得分。
返回一个长度为 n 的整数数组，其中第 i 个元素是节点 i 的 最大得分 。
子图 是原图的一个子集，其顶点和边均来自原图。
连通子图 是一个子图，其中每一对顶点都可以通过该子图的边相互到达。
示例 1：
输入： n = 3, edges = [[0,1],[1,2]], good = [1,0,1]
输出： [1,1,1]
解释：
绿色节点是好节点，红色节点是坏节点。
对于每个节点，包含它的最佳连通子图是整棵树，该树有 2 个好节点和 1 个坏节点，得分为 1。
包含某个节点的其他连通子图可能有相同的得分。
示例 2：
输入： n = 5, edges = [[1,0],[1,2],[1,3],[3,4]], good = [0,1,0,1,1]
输出： [2,3,2,3,3]
解释：
节点 0：最佳连通子图由节点 0, 1, 3, 4 组成，其中有 3 个好节点和 1 个坏节点，得分为 3 - 1 = 2。
节点 1、3 和 4：最佳连通子图由节点 1, 3, 4 组成，其中有 3 个好节点，得分为 3。
节点 2：最佳连通子图由节点 1, 2, 3, 4 组成，其中有 3 个好节点和 1 个坏节点，得分为 3 - 1 = 2。
示例 3：
输入： n = 2, edges = [[0,1]], good = [0,0]
输出： [-1,-1]
解释：
对于每个节点，包含另一节点只会增加一个坏节点，因此每个节点的最佳得分为 -1。
提示：
2 < = n < = 10 5 2 <= n <= 10^5 2<=n<=105
edges.length == n - 1
edges[i] = [ai, bi]
0 <= ai, bi < n
good.length == n
0 <= good[i] <= 1
输入保证 edges 表示一棵有效树。
换根法
以任意节点（如0)为根。
a n s i ans_i ansi任意包含节点i的联通区域的最大分数。
s u b i sub_i subi任意包含节点i,不包括i的父节点的联通区域的最大分数。
一轮DFS（后序遍历)可以计算出sub。
一轮DFS（前序遍历）可以计算出ans。
good[i]如果是0，改成-1.
性质一： s u b i = g o o d [ i ] + ∑ j 是 i 的孩子 m a x ( 0 , s u b [ j ] ) sub_i = good[i] + \sum^{j是i的孩子} max(0,sub[j]) subi=good[i]+∑j是i的孩子max(0,sub[j])
性质二： a n s 0 = s u b 0 ans_0=sub_0 ans0=sub0。
性质三：令par是cur节点父节点。x是包括par节点，不包括cur节点的最大得分。
如果 s u b c u r > 0 sub_{cur}>0 subcur>0,则 x = a n s p a r − s u b c u r ans_{par}-sub_{cur} anspar−subcur;否则x = a n s p a r ans_{par} anspar
a n s c u r = s u b c u r + m a x ( 0 , x ) ans_{cur}=sub_{cur}+max(0,x) anscur=subcur+max(0,x)
代码
核心代码
classCNeiBo{public:static vector<vector<int>>Two(int n,const vector<pair<int,int>>& edges,bool bDirect,int iBase =0){ vector<vector<int>>vNeiBo(n);for(constauto&[i1, i2]: edges){ vNeiBo[i1 - iBase].emplace_back(i2 - iBase);if(!bDirect){ vNeiBo[i2 - iBase].emplace_back(i1 - iBase);}}return vNeiBo;}static vector<vector<int>>Two(int n,const vector<vector<int>>& edges,bool bDirect,int iBase =0){ vector<vector<int>>vNeiBo(n);for(constauto& v : edges){ vNeiBo[v[0]- iBase].emplace_back(v[1]- iBase);if(!bDirect){ vNeiBo[v[1]- iBase].emplace_back(v[0]- iBase);}}return vNeiBo;}static vector<vector<std::pair<int,int>>>Three(int n, vector<vector<int>>& edges,bool bDirect,int iBase =0){ vector<vector<std::pair<int,int>>>vNeiBo(n);for(constauto& v : edges){ vNeiBo[v[0]- iBase].emplace_back(v[1]- iBase, v[2]);if(!bDirect){ vNeiBo[v[1]- iBase].emplace_back(v[0]- iBase, v[2]);}}return vNeiBo;}static vector<vector<std::pair<int,int>>>Three(int n,const vector<tuple<int,int,int>>& edges,bool bDirect,int iBase =0){ vector<vector<std::pair<int,int>>>vNeiBo(n);for(constauto&[u,v,w]: edges){ vNeiBo[u - iBase].emplace_back(v - iBase, w);if(!bDirect){ vNeiBo[v - iBase].emplace_back(u - iBase, w);}}return vNeiBo;}static vector<vector<int>>Mat(vector<vector<int>>& neiBoMat){ vector<vector<int>>neiBo(neiBoMat.size());for(int i =0; i < neiBoMat.size(); i++){for(int j = i +1; j < neiBoMat.size(); j++){if(neiBoMat[i][j]){ neiBo[i].emplace_back(j); neiBo[j].emplace_back(i);}}}return neiBo;}};classSolution{public: vector<int>maxSubgraphScore(int n, vector<vector<int>>& edges, vector<int>& good){this->good = good;for(auto& i :this->good){if(0== i){ i =-1;}} m_vSub.resize(n); m_ans.resize(n);auto neiBo =CNeiBo::Two(n, edges,false);DFS(0,-1, neiBo);DFS2(0,-1, neiBo);return m_ans;}voidDFS(constint cur,constint par,vector<vector<int>>& neiBo){int iChild =0;for(constauto& next : neiBo[cur]){if(par == next){continue;}DFS(next, cur, neiBo);if(m_vSub[next]>0){ iChild += m_vSub[next];}} m_vSub[cur]= good[cur]+ iChild;}voidDFS2(constint cur,constint par, vector<vector<int>>& neiBo){if(-1== par){ m_ans[cur]= m_vSub[cur];}else{constint parS =(m_vSub[cur]>0)?(m_ans[par]- m_vSub[cur]): m_ans[par]; m_ans[cur]= m_vSub[cur];if(parS >0){ m_ans[cur]+= parS;}}for(constauto& next : neiBo[cur]){if(par == next){continue;}DFS2(next, cur, neiBo);}} vector<int> m_vSub, good,m_ans;};单元测试
int n; vector<vector<int>> edges; vector<int> good;TEST_METHOD(TestMethod001){ n =5, edges ={{1,0},{1,2},{1,3},{3,4}}, good ={0,1,0,1,1};auto res =Solution().maxSubgraphScore(n, edges, good);AssertEx({2,3,2,3,3}, res);}TEST_METHOD(TestMethod002){ n =2, edges ={{0,1}}, good ={0,0};;auto res =Solution().maxSubgraphScore(n, edges, good);AssertEx({-1,-1}, res);}TEST_METHOD(TestMethod003){ n =3, edges ={{0,1},{1,2}}, good ={1,0,1};auto res =Solution().maxSubgraphScore(n, edges, good);AssertEx({1,1,1}, res);}TEST_METHOD(TestMethod004){ n =3, edges ={{1,0},{0,2}}, good ={1,1,1};auto res =Solution().maxSubgraphScore(n, edges, good);AssertEx({3,3,3}, res);}扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
