TopCoder SRM 719 Div1 Medium: OwaskiAndTree
問題文中に Overwatch
って単語が出てきてなんだっけとぐぐったら固有名詞 (ゲーム名)だった。
problem
頂点に重みの付いた木上を歩く。 始めて訪ずれたときその重み分の点数を得る。点数が負になる場合は$0$に戻す。 根から始めて自由な位置で終了してよい。 点数の最大値を求めよ。
solution
$0$に戻さない場合の値は木DPで明らか。 $0$に戻す操作は途中で負にすることを許してちょうど$1$回だけ行なうと見做せ、それをした後は戻さない場合のDPから求まる。そのようにすると木の根と葉全ての間のcutを決めてその下側だけ$0$に戻す操作なしで自由に使った場合の最大値になるので、これを木DP。$O(N)$。
implementation
$2$回走らせてる再帰は明らかに融合できる。
#include <bits/stdc++.h>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
class OwaskiAndTree { public: int maximalScore(vector<int> parent, vector<int> pleasure); };
constexpr int root = 0;
int OwaskiAndTree::maximalScore(vector<int> parent, vector<int> pleasure) {
int n = pleasure.size();
vector<vector<int> > children(n);
repeat (i, n - 1) {
children[parent[i]].push_back(i + 1);
}
vector<ll> acc(n); {
function<void (int)> go = [&](int i) {
acc[i] += pleasure[i];
for (int j : children[i]) {
go(j);
if (acc[j] > 0) {
acc[i] += acc[j];
}
}
};
go(root);
}
vector<ll> dp(n); {
function<void (int)> go = [&](int i) {
for (int j : children[i]) {
go(j);
dp[i] += dp[j];
}
setmax(dp[i], acc[i]);
setmax(dp[i], 0ll);
};
go(root);
}
return dp[root];
}