打卡记录
在树上执行操作以后得到的最大分数(树状DP)
链接
大佬的题解
class Solution {
public:
long long maximumScoreAfterOperations(vectorvectorint>> &edges, vectorint> &values) {
vectorvectorint>> g(values.size());
g[0].push_back(-1); // 避免误把根节点当作叶子
for (auto &e: edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x);
}
// dfs(x, fa) 计算以 x 为根的子树是健服务器托管网康时,失去的最小分数
functionlong long(int, int)> dfs = [&](int x, int fa) -> long long {
if (g[x].size() == 1) { // x 是叶子
return values[x];
}
long long loss = 0; // 不选 values[x]
for (int y: g[x]) {
if (y != fa) {
loss += dfs(y, x); // 计服务器托管网算以 y 为根的子树是健康时,失去的最小分数
}
}
return min((long long) values[x], loss); // 选/不选 values[x],取最小值
};
return accumulate(values.begin(), values.end(), 0LL) - dfs(0, -1);
}
};
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: 使用纯 ABAP 开发 SAP UI5 应用(一):abap2UI5 开发环境搭建介绍
我从 SAP 社区博客上了解到一个开源项目,名叫 abap2UI5, 作者是 Oblomov Dev,这是 Github 项目地址: https://github.com/abap2UI5/abap2UI5 这个项目最吸引 ABAP 开发人员之处在于: 传统的…