#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int n, a[N], h[N], c[N], deg[N], id[N], dep[N], mx[N];
bool was[N];
vector<int> grp[N];
int find_id(int i) {
if (id[i] != -1) return id[i];
id[i] = find_id(a[i]);
dep[i] = dep[a[i]] + 1;
return id[i];
}
vector<int> g[N];
void add_edge(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
int who[N];
ll dp[N];
multiset<pair<int, ll>> st[N];
int gfa(int x) { return who[x] == x ? x : who[x] = gfa(who[x]); }
void unite(int x, int y) {
x = gfa(x);
y = gfa(y);
if (st[x].size() < st[y].size())
swap(x, y);
for (auto& p : st[y]) {
st[x].insert(p);
}
st[y].clear();
who[y] = x;
}
void dfs(int x, int fa) {
dp[x] = c[x];
who[x] = x;
for (int y : g[x]) {
if (y == fa) continue;
dfs(y, x);
unite(x, y);
}
while (!st[gfa(x)].empty()) {
auto p = *prev(st[gfa(x)].end());
if (p.first >= h[x]) {
dp[x] += p.second;
st[gfa(x)].erase(prev(st[gfa(x)].end()));
} else break;
}
st[gfa(x)].emplace(h[x], dp[x]);
}
const int inf = 0x3f3f3f3f;
const int M = 100 * N;
int root[N], ls[M], rs[M], tsz;
ll sum[M];
void modify(int& v, int l, int r, int ql, int qr, ll x) {
if (l > r || l > qr || r < ql) return;
if (!v) v = ++tsz;
if (ql <= l && r <= qr) { sum[v] += x; return; }
int mid = l + r >> 1;
modify(ls[v], l, mid, ql, qr, x);
modify(rs[v], mid + 1, r, ql, qr, x);
}
ll query(int v, int l, int r, int p) {
if (!v) return 0ll;
if (l == r) { assert(l == p); return sum[v]; }
int mid = l + r >> 1;
if (p <= mid)
return query(ls[v], l, mid, p) + sum[v];
else
return query(rs[v], mid + 1, r, p) + sum[v];
}
ll solve(vector<int> ver, int g_id) {
vector<int> cyc, tree;
for (int x : ver) {
if (dep[x] == 0)
cyc.push_back(x);
else
tree.push_back(x);
}
for (int x : tree) {
if (dep[a[x]] != 0)
add_edge(x, a[x]);
}
for (int x : tree) {
if (dep[x] == 1) {
dfs(x, x);
vector<pair<int, ll>> vec;
for (auto& p : st[gfa(x)])
vec.push_back(p);
// for (int i = vec.size() - 2; i >= 0; i--) {
// assert(vec[i].second >= vec[i + 1].second);
// }
vector<pair<int, ll>> new_vec;
for (auto& p : vec) {
while (new_vec.size() > 0 && new_vec.back().second <= p.second)
new_vec.pop_back();
new_vec.push_back(p);
}
int prv = 0;
for (auto& p : new_vec) {
if (prv <= p.first) {
modify(root[g_id], 0, inf, prv, p.first, p.second);
prv = p.first + 1;
}
}
}
}
vector<int> vals;
ll tot_sum = 0;
for (int x : ver)
vals.push_back(h[x]), tot_sum += c[x];
//sort(vals.begin(), vals.end());
//vals.erase(unique(vals.begin(), vals.end()), vals.end());
map<int, ll> mp;
for (int x : cyc)
mp[h[x]] += c[x];
ll ans = 0;
for (int v : vals) {
ans = max(ans, mp[v] + query(root[g_id], 0, inf, v));
}
return tot_sum - ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &a[i], &h[i], &c[i]);
}
for (int i = 1; i <= n; i++) {
deg[a[i]] += 1;
}
vector<int> que;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
que.push_back(i);
}
}
for (int i = 0; i < que.size(); i++) {
int x = que[i];
deg[a[x]] -= 1;
if (deg[a[x]] == 0) {
que.push_back(a[x]);
}
}
que.clear();
for (int i = 1; i <= n; i++)
if (deg[i] > 0)
que.push_back(i);
for (int i = 1; i <= n; i++)
id[i] = -1, dep[i] = 0;
vector<vector<int>> cycs;
for (int x : que) {
if (!was[x]) {
vector<int> cyc;
int i = x;
while (!was[i]) {
was[i] = true;
id[i] = cycs.size();
cyc.push_back(i);
i = a[i];
}
cycs.push_back(cyc);
}
}
for (int i = 1; i <= n; i++) {
id[i] = find_id(i);
grp[id[i]].push_back(i);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
if (grp[i].empty()) continue;
ans += solve(grp[i], i);
}
printf("%lld\n", ans);
}
/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
14
5
1 1 1
2 2 1
4 3 1
3 3 1
4 3 1
0
20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771
2711043927
20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030
4012295156
*/
Compilation message
worst_reporter2.cpp: In function 'void modify(int&, int, int, int, int, long long int)':
worst_reporter2.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = l + r >> 1;
| ~~^~~
worst_reporter2.cpp: In function 'long long int query(int, int, int, int)':
worst_reporter2.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int mid = l + r >> 1;
| ~~^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int i = 0; i < que.size(); i++) {
| ~~^~~~~~~~~~~~
worst_reporter2.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
worst_reporter2.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | scanf("%d%d%d", &a[i], &h[i], &c[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19156 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19156 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19168 KB |
Output is correct |
| 4 |
Correct |
10 ms |
19056 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
20024 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19156 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19156 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19168 KB |
Output is correct |
| 4 |
Correct |
10 ms |
19056 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
20024 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19156 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19156 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19168 KB |
Output is correct |
| 4 |
Correct |
10 ms |
19056 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
20024 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
