#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)
struct E {
int to, w;
};
const ll INF = 1e18;
const int N = 2e5 + 5;
vector<E> g[N];
ll dp[N][2][2];
void dfs(int node, int x, int anc) {
ll mx1 = -INF, mx2 = -INF, mx3 = -INF, s = 0;
multiset<ll> st;
for (E e : g[node]) {
if (e.to != anc) {
dfs(e.to, e.w, node);
ll a = max(dp[e.to][0][0], dp[e.to][0][1]);
mx1 = max(mx1, dp[e.to][0][1] + e.w - a);
mx2 = max(mx2, max(dp[e.to][0][1], dp[e.to][1][1]) + e.w - a);
mx3 = max(mx3, max(dp[e.to][1][0], dp[e.to][1][1]) - a);
s += a;
st.insert(dp[e.to][0][1] + e.w - a);
}
}
dp[node][0][1] = s;
dp[node][0][0] = s + mx1 + x;
dp[node][1][0] = s + mx2 + x;
dp[node][1][1] = s + mx3;
if (st.size() > 1) {
for (E e : g[node]) {
if (e.to != anc) {
ll a = max(dp[e.to][0][0], dp[e.to][0][1]),
b = dp[e.to][1][1] + e.w - a,
c = dp[e.to][0][1] + e.w - a;
st.erase(st.find(c));
dp[node][1][1] = max(dp[node][1][1], s + *st.rbegin() + max(b, c));
st.insert(c);
}
}
}
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int x, y, w;
cin >> x >> y >> w;
x--, y--;
g[x].push_back({ y, w });
g[y].push_back({ x, w });
}
dfs(0, -1, -1);
cout << max(dp[0][0][1], dp[0][1][1]);
return 0;
}
Compilation message
beads.cpp:41:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable : 4996)
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5044 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
5120 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
5 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
5 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5044 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
5120 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
5 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
5 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
5 ms |
4992 KB |
Output is correct |
19 |
Correct |
5 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5044 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
5120 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
5 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
5 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
5 ms |
4992 KB |
Output is correct |
19 |
Correct |
5 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
23 |
Correct |
8 ms |
5376 KB |
Output is correct |
24 |
Correct |
9 ms |
5348 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
12 ms |
5760 KB |
Output is correct |
27 |
Correct |
11 ms |
5760 KB |
Output is correct |
28 |
Correct |
15 ms |
6144 KB |
Output is correct |
29 |
Correct |
14 ms |
6144 KB |
Output is correct |
30 |
Correct |
14 ms |
6016 KB |
Output is correct |
31 |
Correct |
14 ms |
6784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5044 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
5120 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
5 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
5 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
5 ms |
4992 KB |
Output is correct |
19 |
Correct |
5 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
23 |
Correct |
8 ms |
5376 KB |
Output is correct |
24 |
Correct |
9 ms |
5348 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
12 ms |
5760 KB |
Output is correct |
27 |
Correct |
11 ms |
5760 KB |
Output is correct |
28 |
Correct |
15 ms |
6144 KB |
Output is correct |
29 |
Correct |
14 ms |
6144 KB |
Output is correct |
30 |
Correct |
14 ms |
6016 KB |
Output is correct |
31 |
Correct |
14 ms |
6784 KB |
Output is correct |
32 |
Correct |
42 ms |
8532 KB |
Output is correct |
33 |
Correct |
44 ms |
8412 KB |
Output is correct |
34 |
Correct |
47 ms |
8448 KB |
Output is correct |
35 |
Correct |
254 ms |
19704 KB |
Output is correct |
36 |
Correct |
258 ms |
19832 KB |
Output is correct |
37 |
Correct |
254 ms |
19704 KB |
Output is correct |
38 |
Correct |
382 ms |
28516 KB |
Output is correct |
39 |
Correct |
401 ms |
26972 KB |
Output is correct |
40 |
Correct |
368 ms |
26336 KB |
Output is correct |
41 |
Correct |
336 ms |
32364 KB |
Output is correct |