#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long
template <class _T>
bool chmin(_T &x, const _T &y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag = false;
if ( x < y ){
x = y; flag |= true;
}
return flag;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector <pair<int,int>> g[n];
for ( int i = 1; i < n; i++ ){
int x, y, w; cin >> x >> y >> w;
g[--x].pb({--y, w});
g[y].pb({x, w});
}
const int inf = 1e18 + 1;
vector <array<int,2>> dp(n);
multiset <int> s[n];
vector <int> par_w(n);
function <void(int,int,int)> dfs = [&](int x, int par, int prev){
int cnt = 0;
par_w[x] = prev;
for ( auto [to, w]: g[x] ){
if ( to == par ) continue;
dfs(to, x, w);
cnt += dp[to][1];
s[x].insert(dp[to][0] - dp[to][1] + w);
}
dp[x][0] = cnt;
if ( !s[x].empty() ){
dp[x][1] = cnt + *s[x].rbegin() + par_w[x];
}
chmax(dp[x][1], dp[x][0]);
};
int res = 0;
function <void(int,int)> reRoot = [&](int x, int par){
chmax(res, dp[x][0]);
auto erase = [&](int x, int val){
s[x].erase(s[x].find(val));
};
for ( auto [to, w]: g[x] ){
if ( to == par ) continue;
par_w[x] = w; par_w[to] = 0;
erase(x, -dp[to][1] + dp[to][0] + w);
dp[x][0] -= dp[to][1];
dp[x][1] = dp[x][0];
if ( !s[x].empty() ){
chmax(dp[x][1], dp[x][0] + *s[x].rbegin() + par_w[x]);
}
s[to].insert(dp[x][0] + w - dp[x][1]);
dp[to][0] += dp[x][1];
dp[to][1] = max(dp[to][0], dp[to][0] + *s[to].rbegin() + par_w[to]);
reRoot(to, x);
swap(x, to);
par_w[x] = w; par_w[to] = 0;
erase(x, -dp[to][1] + dp[to][0] + w);
dp[x][0] -= dp[to][1];
dp[x][1] = dp[x][0];
if ( !s[x].empty() ){
chmax(dp[x][1], dp[x][0] + *s[x].rbegin() + par_w[x]);
}
s[to].insert(dp[x][0] + w - dp[x][1]);
dp[to][0] += dp[x][1];
dp[to][1] = max(dp[to][0], dp[to][0] + *s[to].rbegin() + par_w[to]);
swap(x, to);
}
};
dfs(0, -1, 0);
reRoot(0, -1);
cout << res;
cout << '\n';
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:39:15: warning: unused variable 'inf' [-Wunused-variable]
39 | const int inf = 1e18 + 1;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
320 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
320 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
320 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
320 KB |
Output is correct |
23 |
Correct |
5 ms |
1236 KB |
Output is correct |
24 |
Correct |
5 ms |
1300 KB |
Output is correct |
25 |
Correct |
5 ms |
1364 KB |
Output is correct |
26 |
Correct |
8 ms |
2388 KB |
Output is correct |
27 |
Correct |
8 ms |
2388 KB |
Output is correct |
28 |
Correct |
10 ms |
2392 KB |
Output is correct |
29 |
Correct |
10 ms |
2252 KB |
Output is correct |
30 |
Correct |
9 ms |
2252 KB |
Output is correct |
31 |
Correct |
10 ms |
3156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
320 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
320 KB |
Output is correct |
23 |
Correct |
5 ms |
1236 KB |
Output is correct |
24 |
Correct |
5 ms |
1300 KB |
Output is correct |
25 |
Correct |
5 ms |
1364 KB |
Output is correct |
26 |
Correct |
8 ms |
2388 KB |
Output is correct |
27 |
Correct |
8 ms |
2388 KB |
Output is correct |
28 |
Correct |
10 ms |
2392 KB |
Output is correct |
29 |
Correct |
10 ms |
2252 KB |
Output is correct |
30 |
Correct |
9 ms |
2252 KB |
Output is correct |
31 |
Correct |
10 ms |
3156 KB |
Output is correct |
32 |
Correct |
46 ms |
10572 KB |
Output is correct |
33 |
Correct |
60 ms |
10572 KB |
Output is correct |
34 |
Correct |
47 ms |
10612 KB |
Output is correct |
35 |
Correct |
334 ms |
42376 KB |
Output is correct |
36 |
Correct |
278 ms |
42184 KB |
Output is correct |
37 |
Correct |
298 ms |
42392 KB |
Output is correct |
38 |
Correct |
358 ms |
41576 KB |
Output is correct |
39 |
Correct |
342 ms |
41456 KB |
Output is correct |
40 |
Correct |
342 ms |
41400 KB |
Output is correct |
41 |
Correct |
319 ms |
51016 KB |
Output is correct |