#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define val(x) (((x) == nullptr) ? 0 : ((x) -> s))
#define int long long
using namespace std;
const int N = 3e5 + 3, M = 1e9, inf = 1e9;
int n, m, dp[N], s[N];
vector <pair <int, int> > q[N];
struct node {
node * l = nullptr, * r = nullptr;
int s = 0;
};
node * st1[N], * st2[N];
void update(node * t, int tl, int tr, int x, int y) {
if (tl == tr) {
t -> s += y;
return;
}
int tm = (tl + tr) >> 1LL;
if (x <= tm) {
if (t -> l == nullptr) {
t -> l = new node();
}
update(t -> l, tl, tm, x, y);
} else {
if (t -> r == nullptr) {
t -> r = new node();
}
update(t -> r, tm + 1, tr, x, y);
}
t -> s = val(t -> l) + val(t -> r);
}
int getsum(node * t, int tl, int tr, int l, int r) {
if (t == nullptr || tl > r || tr < l) {
return 0;
}
if (tl >= l && tr <= r) {
return t -> s;
}
int tm = (tl + tr) >> 1LL;
return getsum(t -> l, tl, tm, l, r) + getsum(t -> r, tm + 1, tr, l, r);
}
int f(int v, int x) {
int y = x * getsum(st1[v], 0, M, 0, x) - getsum(st2[v], 0, M, 0, x);
int z = getsum(st2[v], 0, M, x + 1, M) - x * getsum(st1[v], 0, M, x + 1, M);
return y + z;
}
pair <int, int> getans(int v, int to) {
int l = -s[to], r = 1e9 - s[to], magic = 31;
while (magic--) {
int mid = (l + r) >> 1LL;
if (f(v, s[to] + mid) > f(v, s[to] + mid + 1)) {
l = mid;
} else {
r = mid;
}
}
return {f(v, s[to] + r), r};
}
void dfs(int v, int p) {
st1[v] = new node(), st2[v] = new node();
int mx = -1, big = -1;
for (auto i : q[v]) {
int to = i.fi, w = i.se;
if (to != p) {
dfs(to, v);
dp[v] += dp[to];
s[to] += w;
update(st1[v], 0, M, s[to], 1);
update(st2[v], 0, M, s[to], s[to]);
}
}
int res = inf;
for (auto i : q[v]) {
int to = i.fi, w = i.se;
if (to != p) {
pair <int, int> tmp = getans(v, to);
if (tmp.fi < res) {
res = tmp.fi, s[v] = s[to] + tmp.se;
}
}
}
if (res == inf) {
res = 0;
}
dp[v] += res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for (int i = 2; i <= n + m; i++) {
int x, y;
cin>>x>>y;
q[x].pb({i, y});
q[i].pb({x, y});
}
dfs(1, 1);
cout<<dp[1];
}
Compilation message
fireworks.cpp: In function 'void dfs(long long int, long long int)':
fireworks.cpp:90:24: warning: unused variable 'w' [-Wunused-variable]
int to = i.fi, w = i.se;
^
fireworks.cpp:77:9: warning: unused variable 'mx' [-Wunused-variable]
int mx = -1, big = -1;
^~
fireworks.cpp:77:18: warning: unused variable 'big' [-Wunused-variable]
int mx = -1, big = -1;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
