#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1000100
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
using namespace std;
int n, p[N], val[N], status[N], total, Del[N], DEG[N];
int lazy[N << 2];
long long IT[N << 2];
bool Disabled[N];
vector<pp> e[N];
void dfs(int u) {
for (pp t : e[u]) {
int v = t.first;
int c = t.second;
if (v != p[u]) {
p[v] = u;
val[v] = c;
dfs(v);
}
}
}
void Build(int k, int l, int r) {
lazy[k] = 0;
if (l == r) {
if (l <= n) {
IT[k] = 1e18;
Disabled[l] = true;
}
else {
IT[k] = val[l];
Disabled[l] = false;
status[l] = 1;
total++;
}
return;
}
int m = (l + r) >> 1;
Build(k << 1, l, m);
Build(k << 1 | 1, m + 1, r);
IT[k] = min(IT[k << 1], IT[k << 1 | 1]);
}
void Down(int k) {
if (lazy[k] == 0) return;
lazy[k << 1] += lazy[k];
lazy[k << 1 | 1] += lazy[k];
IT[k << 1] += lazy[k];
IT[k << 1 | 1] += lazy[k];
lazy[k] = 0;
}
void Set(int k, int l, int r, int u, int val) {
if (l == r) {
IT[k] = val;
lazy[k] = 0;
return;
}
Down(k);
int m = (l + r) >> 1;
if (u <= m) Set(k << 1, l, m, u, val);
else Set(k << 1 | 1, m + 1, r, u, val);
IT[k] = min(IT[k << 1], IT[k << 1 | 1]);
}
int root;
void Research(int k, int l, int r) {
if (IT[k] > 0) return;
if (l == r) {
Disabled[l] = true;
IT[k] = 1e18;
total -= 2;
status[l] = -1;
if (p[l] == -1) return;
Del[p[l]]++;
if (Del[p[l]] * 2 >= (int)e[p[l]].size() - (p[l] != root)) {
for (pp t : e[p[l]]) {
int v = t.first;
if (v != p[p[l]]) {
total -= status[v];
status[v] = 0;
if (!Disabled[v]) {
Set(1, 1, n, v, 1e18);
Disabled[v] = true;
}
}
}
Disabled[p[l]] = false;
status[p[l]] = 1;
total++;
Set(1, 1, n, p[l], val[p[l]]);
}
return;
}
Down(k);
int m = (l + r) >> 1;
Research(k << 1, l, m);
Research(k << 1 | 1, m + 1, r);
IT[k] = min(IT[k << 1], IT[k << 1 | 1]);
}
int main() {
//Enter
IO;
int m;
cin >> n >> m;
long long result = 0;
FOR(i, 2, n + m) {
int u, c;
cin >> u >> c;
result += c;
e[i].push_back(pp(u, c));
e[u].push_back(pp(i, c));
DEG[i]++;
DEG[u]++;
}
int root = 0;
FOR(i, 1, n) if (DEG[i] == 1) root = i;
p[root] = -1;
dfs(root);
// Initialization
Build(1, 1, n + m);
n += m;
// Solve
while (total > 0) {
result -= 1ll * IT[1] * total;
lazy[1] -= IT[1];
IT[1] = 0;
Research(1, 1, n);
}
cout << result;
}
Compilation message
fireworks.cpp: In function 'void Research(int, int, int)':
fireworks.cpp:94:45: warning: overflow in implicit constant conversion [-Woverflow]
Set(1, 1, n, v, 1e18);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
92848 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
92848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
92848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
92848 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
92848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
92848 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
92848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
