#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n <= 2) return cout << 0, 0;
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
vector<vector<int>> f(2, vector<int>(n, 0));
function<void(int, int)> dfs = [&](int u, int p) {
f[1][u] = -2e9;
f[0][u] = 0;
for (pair<int, int>& e : adj[u]) {
int v = e.first;
int c = e.second;
if (v == p) continue;
dfs(v, u);
f[0][u] += max(f[0][v], f[1][v] + c);
}
for (pair<int, int>& e : adj[u]) {
int v = e.first;
int c = e.second;
if (v == p) continue;
f[1][u] = max(f[1][u], f[0][u] - max(f[0][v], f[1][v] + c) + f[0][v] + c);
}
if (p == -1) {
vector<int> best;
for (pair<int, int>& e : adj[u]) {
int v = e.first;
int c = e.second;
if (v == p) continue;
best.emplace_back(f[0][v] + c - max(f[0][v], f[1][v] + c));
int i = best.size() - 1;
while (i > 0 && best[i] > best[i - 1]) swap(best[i], best[i - 1]), i--;
if (best.size() > 2) best.pop_back();
}
if (best.size() == 2) f[0][u] += max(0, best[0] + best[1]);
}
};
int res = 0;
vector<int> random(n);
iota(random.begin(), random.end(), 0);
random_shuffle(random.begin(), random.end());
for (int i = 0; i < min(100, n); i++) dfs(random[i], -1), res = max(res, f[0][random[i]]);
cout << res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
232 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
224 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
232 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
224 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
232 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
224 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
232 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
224 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |