# HackerRank Performance Optimization: D. Skipping Subpath Sum

,

https://www.hackerrank.com/contests/optimization-oct17/challenges/skipping-subpath-sum

## problem

• 頂点$u, v$が与えられる。$u, v$間の唯一のpathについて、偶数番目の頂点の重みの総和と奇数番目の頂点の重みの総和のうち大きい方を答えよ。

## 知見

• 順に伸ばしていって総和が負になったらリセットする感じ
• 名前を知らないだけでみんなやってるやつ

## implementation

...

#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

vector<int> skippingSubpathSum(int n, vector<int> const & c, vector<vector<int> > const & graph, vector<pair<int, int> > const & queries) {
// prepare
constexpr int root = 0;
vector<int16_t> parent(n, -1);
vector<int16_t> depth(n, -1); {
function<void (int)> go = [&](int i) {
for (int j : graph[i]) if (parent[j] == -1) {
parent[j] = i;
depth[j] = depth[i] + 1;
go(j);
}
};
parent[root] = root;
depth[root] = 0;
go(root);
}
// solve
for (auto query : queries) {
int result[2] = {};
int acc[2] = {};
int path_size = 0;
auto kadane = [&](int c_i) {
int i = (path_size ++) & 1;
acc[i] += c_i;
setmax(acc[i], 0);
setmax(result[i], acc[i]);
};
// run
int u, v; tie(u, v) = query;
if (depth[u] < depth[v]) {
swap(u, v);
}
assert (depth[u] >= depth[v]);
for (int depth_u = depth[u]; depth_u > depth[v]; ) {
u = parent[u];
-- depth_u;
}
assert (depth[u] == depth[v]);
vector<int> stk;
while (u != v) {
stk.push_back(c[v]);
u = parent[u];
v = parent[v];
}