#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct info {
ll f, s;
bool operator<(const info &o) const {
if(f == o.f)
return s < o.s;
return f < o.f;
}
bool operator>(const info &o) const {
if(f == o.f)
return s > o.s;
return f > o.f;
}
};
using ds = priority_queue<info, vector<info>, greater<info>>;
void solve() {
int n;
ll s;
cin >> n >> s;
ll start = s;
vector<ll> c(n + 1);
vector<vector<int>> adj(n + 1);
for(int i = 1, u; i <= n; i++) {
cin >> c[i] >> u;
adj[u].push_back(i);
adj[i].push_back(u);
}
auto merge = [&](info &a, info &b) {
ll net = a.s - a.f + b.s - b.f;
a = {max(a.f, a.f - a.s + b.f), net + max(a.f, a.f - a.s + b.f)};
};
auto dfs = [&](auto &&self, int u, int p) -> ds {
ds pq;
for(auto &v : adj[u])
if(v != p) {
ds re = self(self, v, u);
if(re.size() > pq.size())
swap(re, pq);
while(re.size() > 0) {
pq.push(re.top());
re.pop();
}
}
info us = {max(-c[u], 0ll), max(c[u], 0ll)};
while(!pq.empty() && (us.s <= us.f || us.s >= pq.top().f)) {
auto v = pq.top();
merge(us, v);
pq.pop();
}
if(us.f < us.s)
pq.push(us);
return pq;
};
ds v = dfs(dfs, 0, -1);
while(!v.empty()) {
info seg = v.top();
v.pop();
if(s < seg.f)
break;
s += seg.s - seg.f;
}
cout << s - start << '\n';
}
int main() {
int t = 1;
// cin >> t;
while(t--)
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |