作者推荐
【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目
本文涉及知识点
深度优先搜索
LeetCode2538. 最大价值和与最小价值和的差值
给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。
一条路径的 价值和 是这条路径上所有节点的价值之和。
你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。
请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。
示例 1：
输入：n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
输出：24
解释：上图展示了以节点 2 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径节点为 [2,1,3,4]：价值为 [7,8,6,10] ，价值和为 31 。
- 第二条路径节点为 [2] ，价值为 [7] 。
最大路径和与最小路径和的差值为 24 。24 是所有方案中的最大开销。
示例 2：
输入：n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
输出：2
解释：上图展示了以节点 0 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。 - 第一条路径包含节点 [0,1,2]：价值为 [1,1,1] ，价值和为 3 。
- 第二条路径节点为 [0] ，价值为 [1] 。
最大路径和与最小路径和的差值为 2 。2 是所有方案中的最大开销。
提示：
1 <= n <= 105
edges.length == n - 1
0 <= ai, bi <= n - 1
edges 表示一棵符合题面要求的树。
price.length == n
1 <= price[i] <= 105
深度优先搜索
以0为根节点的树，来分析问题。节点和终点可能的情况。
一，都是叶子节点。
二，一个叶子节点，一个支节点。不可能，枝节点换成根节点更长。
三，一个叶子节点，一个根节点。可能。比如：独子树。
四，两个支节点，不可能。其中1个换成叶子节点更长。
五，一个支节点，一个根节点。不可能。支节点换成叶子节点更长。
总结：只有两种情况需要考虑：
两个叶子节点，枚举它们的公共祖先。
根节点和叶子节点。
DFS 返回本子树 从 子树的根到叶子的最大价值，两个值：包括叶子和不包括叶子。
代码
核心代码
class CNeiBo2 { public: CNeiBo2(int n, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase) { m_vNeiB.resize(n); } CNeiBo2(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase) { m_vNeiB.resize(n); for (const auto& v : edges) { m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase); } } } inline void Add(int iNode1, int iNode2) { iNode1 -= m_iBase; iNode2 -= m_iBase; m_vNeiB[iNode1].emplace_back(iNode2); if (!m_bDirect) { m_vNeiB[iNode2].emplace_back(iNode1); } } const int m_iN; const bool m_bDirect; const int m_iBase; vector<vector<int>> m_vNeiB; }; template<class ELE> void MaxSelf(ELE* seft, const ELE& other) { *seft = max(*seft, other); } class Solution { public: long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) { m_price = price; CNeiBo2 neiBo(n, edges, false); DFS(neiBo.m_vNeiB, 0, -1); return m_llRet; } pair<long long, long long> DFS(vector<vector<int>>& neiBo, int cur, int par) { long long l1 = m_price[cur], l2 = 0; for (const auto& next : neiBo[cur]) { if (next == par) { continue; } const auto [ll1,ll2] = DFS(neiBo, next, cur); MaxSelf(&m_llRet, l1+ll2); MaxSelf(&m_llRet, ll1 + l2); MaxSelf(&l1, m_price[cur] + ll1); MaxSelf(&l2, m_price[cur] + ll2); } return make_pair(l1,l2); } vector<int> m_price; long long m_llRet = 0; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector<int>> lcp; { Solution sln; lcp = { {4,0,2,0},{0,3,0,1},{2,0,2,0},{0,1,0,1} }; auto res = sln.findTheString(lcp); Assert(res,"abab"); } { Solution sln; lcp = { {4,3,2,1},{3,3,2,1},{2,2,2,1},{1,1,1,1} }; auto res = sln.findTheString(lcp); Assert(res, "aaaa"); } { Solution sln; lcp = { {4,3,2,1},{3,3,2,1},{2,2,2,1},{1,1,1,3} }; auto res = sln.findTheString(lcp); Assert(res, ""); } }
2023年2月
class Solution {
public:
long long maxOutput(int n, vector<vector>& edges, vector& price) {
m_vDirect.resize(n);
m_vMaxValueMaxValueExcSelf.resize(n);
for (const auto& v : edges)
{
m_vDirect[v[0]].push_back(v[1]);
m_vDirect[v[1]].push_back(v[0]);
}
dfs(0, -1, price);
return m_llRet;
}
void dfs(int iCur, int iParent, const vector<int>& price) { long long llMaxValue = price[iCur]; long long llMaxValueExcMyself = 0; for (const auto& next : m_vDirect[iCur]) { if (next == iParent) { continue; } dfs(next, iCur, price); const auto& nextValue = m_vMaxValueMaxValueExcSelf[next]; m_llRet = max(m_llRet, max(llMaxValue + nextValue.second, llMaxValueExcMyself + nextValue.first)); llMaxValue = max(llMaxValue, nextValue.first + price[iCur]); llMaxValueExcMyself = max(llMaxValueExcMyself, nextValue.second + price[iCur]); } m_vMaxValueMaxValueExcSelf[iCur] = std::make_pair(llMaxValue, llMaxValueExcMyself); } vector<std::pair<long long, long long>> m_vMaxValueMaxValueExcSelf; vector<vector<int>> m_vDirect; long long m_llRet = 0;
};
2023年9月
class Solution {
public:
long long maxOutput(int n, vector<vector>& edges, vector& price) {
CNeiBo2 neibo(n, edges, false);
std::multimap<long long, int>mMaxPrice, mMaxPriceInclueLeaf;
dfs(0, -1, mMaxPrice, mMaxPriceInclueLeaf, neibo, price);
return m_llRet;
}
void dfs(int cur, const int parent, std::multimap<long long,int>& mMaxPrice, std::multimap<long long, int>& mMaxPriceInclueLeaf,const CNeiBo2& neiBo, vector& price)
{
for (const auto& next : neiBo.m_vNeiB[cur])
{
if (parent == next)
{
continue;
}
std::multimap<long long, int> m, mLeaf;
dfs(next, cur, m, mLeaf, neiBo, price);
if (m.empty())
{
mMaxPrice.emplace( 0, next);
mMaxPriceInclueLeaf.emplace(price[next], next);
}
else
{
mMaxPrice.emplace(m.rbegin()->first + price[next], next);
mMaxPriceInclueLeaf.emplace(mLeaf.rbegin()->first + price[next], next);
}
}
while (mMaxPrice.size() > 2)
{
mMaxPrice.erase(mMaxPrice.begin());
}
while (mMaxPriceInclueLeaf.size() > 2)
{
mMaxPriceInclueLeaf.erase(mMaxPriceInclueLeaf.begin());
}
long long curRet = GetMax(mMaxPrice, mMaxPriceInclueLeaf);
if (0 != curRet)
{
curRet += price[cur];
}
if (mMaxPriceInclueLeaf.size())
{
curRet = max(curRet, mMaxPriceInclueLeaf.rbegin()->first);
}
m_llRet = max(m_llRet, curRet);
}
long long GetMax(const std::multimap<long long, int>& mMaxPrice, const std::multimap<long long, int>& mMaxPriceInclueLeaf)
{
if (mMaxPrice.empty())
{
return 0;
}
if (1 == mMaxPrice.size())
{
return mMaxPrice.begin()->first;
}
if (mMaxPrice.rbegin()->second != mMaxPriceInclueLeaf.rbegin()->second)
{
return mMaxPrice.rbegin()->first + mMaxPriceInclueLeaf.rbegin()->first;
}
return max(mMaxPrice.begin()->first + mMaxPriceInclueLeaf.rbegin()->first, mMaxPrice.rbegin()->first + mMaxPriceInclueLeaf.begin()->first);
}
long long m_llRet = 0;
};
