【图论 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++**实现。