#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 100000;
int const inf = 1000000000;
ll dp[1 + nmax][2];
vector<pair<int,int>> g[1 + nmax];
void dfs(int node, int parent, int up){
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
if(to == parent)
g[node].erase(g[node].begin() + h);
}
ll sum = 0;
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
dfs(to, node, g[node][h].second);
sum += dp[to][1];
}
dp[node][0] = sum;
dp[node][1] = sum;
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
int cost = g[node][h].second;
dp[node][1] = max(dp[node][1], sum - dp[to][1] + dp[to][0] + cost + up);
}
}
ll dp2[1 + nmax][2];
ll maxrange(vector<pair<ll,int>> &temp, int avoid){
for(int i = 0; i < temp.size(); i++)
if(temp[i].second != avoid)
return temp[i].first;
return 0;
}
void dfs2(int node, int parent, int up){
dp2[node][1] = max(dp2[node][0], dp2[node][1]);
ll sum = dp2[node][1];
vector<pair<ll,int>> temp;
temp.push_back({-dp2[node][1] + dp2[node][0] + up, parent});
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
sum += dp[to][1];
temp.push_back({-dp[to][1] + dp[to][0] + g[node][h].second, to});
}
sort(temp.begin(), temp.end());
reverse(temp.begin(), temp.end());
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
dp2[to][0] = sum - dp[to][1];
dp2[to][1] = dp2[to][0] + maxrange(temp, to) + g[node][h].second;
}
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
int cost = g[node][h].second;
dfs2(to, node, cost);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1;i < n; i++){
int x, y, cost;
cin >> x >> y >> cost;
g[x].push_back({y, cost});
g[y].push_back({x, cost});
}
dfs(1, 0, 0);
dp2[1][1] = 0;
dfs2(1, 0, -inf);
ll result = 0;
for(int i = 1;i <= n; i++)
result = max(result, dp[i][0] + dp2[i][1]);
cout << result;
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
beads.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
beads.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
beads.cpp: In function 'll maxrange(std::vector<std::pair<long long int, int> >&, int)':
beads.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < temp.size(); i++)
~~^~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int, int)':
beads.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
beads.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
beads.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2560 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
6 ms |
2688 KB |
Output is correct |
5 |
Correct |
6 ms |
2688 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
6 ms |
2688 KB |
Output is correct |
8 |
Correct |
6 ms |
2688 KB |
Output is correct |
9 |
Correct |
6 ms |
2688 KB |
Output is correct |
10 |
Correct |
6 ms |
2688 KB |
Output is correct |
11 |
Correct |
6 ms |
2688 KB |
Output is correct |
12 |
Correct |
6 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2560 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
6 ms |
2688 KB |
Output is correct |
5 |
Correct |
6 ms |
2688 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
6 ms |
2688 KB |
Output is correct |
8 |
Correct |
6 ms |
2688 KB |
Output is correct |
9 |
Correct |
6 ms |
2688 KB |
Output is correct |
10 |
Correct |
6 ms |
2688 KB |
Output is correct |
11 |
Correct |
6 ms |
2688 KB |
Output is correct |
12 |
Correct |
6 ms |
2688 KB |
Output is correct |
13 |
Correct |
6 ms |
2688 KB |
Output is correct |
14 |
Correct |
6 ms |
2688 KB |
Output is correct |
15 |
Correct |
6 ms |
2688 KB |
Output is correct |
16 |
Correct |
7 ms |
2688 KB |
Output is correct |
17 |
Correct |
6 ms |
2688 KB |
Output is correct |
18 |
Correct |
6 ms |
2688 KB |
Output is correct |
19 |
Correct |
6 ms |
2688 KB |
Output is correct |
20 |
Correct |
6 ms |
2688 KB |
Output is correct |
21 |
Correct |
6 ms |
2688 KB |
Output is correct |
22 |
Correct |
6 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2560 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
6 ms |
2688 KB |
Output is correct |
5 |
Correct |
6 ms |
2688 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
6 ms |
2688 KB |
Output is correct |
8 |
Correct |
6 ms |
2688 KB |
Output is correct |
9 |
Correct |
6 ms |
2688 KB |
Output is correct |
10 |
Correct |
6 ms |
2688 KB |
Output is correct |
11 |
Correct |
6 ms |
2688 KB |
Output is correct |
12 |
Correct |
6 ms |
2688 KB |
Output is correct |
13 |
Correct |
6 ms |
2688 KB |
Output is correct |
14 |
Correct |
6 ms |
2688 KB |
Output is correct |
15 |
Correct |
6 ms |
2688 KB |
Output is correct |
16 |
Correct |
7 ms |
2688 KB |
Output is correct |
17 |
Correct |
6 ms |
2688 KB |
Output is correct |
18 |
Correct |
6 ms |
2688 KB |
Output is correct |
19 |
Correct |
6 ms |
2688 KB |
Output is correct |
20 |
Correct |
6 ms |
2688 KB |
Output is correct |
21 |
Correct |
6 ms |
2688 KB |
Output is correct |
22 |
Correct |
6 ms |
2688 KB |
Output is correct |
23 |
Correct |
9 ms |
3072 KB |
Output is correct |
24 |
Correct |
9 ms |
3200 KB |
Output is correct |
25 |
Correct |
9 ms |
3072 KB |
Output is correct |
26 |
Correct |
12 ms |
3584 KB |
Output is correct |
27 |
Correct |
12 ms |
3584 KB |
Output is correct |
28 |
Correct |
11 ms |
3968 KB |
Output is correct |
29 |
Correct |
11 ms |
3712 KB |
Output is correct |
30 |
Correct |
11 ms |
3712 KB |
Output is correct |
31 |
Correct |
12 ms |
4352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2560 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
6 ms |
2688 KB |
Output is correct |
5 |
Correct |
6 ms |
2688 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
6 ms |
2688 KB |
Output is correct |
8 |
Correct |
6 ms |
2688 KB |
Output is correct |
9 |
Correct |
6 ms |
2688 KB |
Output is correct |
10 |
Correct |
6 ms |
2688 KB |
Output is correct |
11 |
Correct |
6 ms |
2688 KB |
Output is correct |
12 |
Correct |
6 ms |
2688 KB |
Output is correct |
13 |
Correct |
6 ms |
2688 KB |
Output is correct |
14 |
Correct |
6 ms |
2688 KB |
Output is correct |
15 |
Correct |
6 ms |
2688 KB |
Output is correct |
16 |
Correct |
7 ms |
2688 KB |
Output is correct |
17 |
Correct |
6 ms |
2688 KB |
Output is correct |
18 |
Correct |
6 ms |
2688 KB |
Output is correct |
19 |
Correct |
6 ms |
2688 KB |
Output is correct |
20 |
Correct |
6 ms |
2688 KB |
Output is correct |
21 |
Correct |
6 ms |
2688 KB |
Output is correct |
22 |
Correct |
6 ms |
2688 KB |
Output is correct |
23 |
Correct |
9 ms |
3072 KB |
Output is correct |
24 |
Correct |
9 ms |
3200 KB |
Output is correct |
25 |
Correct |
9 ms |
3072 KB |
Output is correct |
26 |
Correct |
12 ms |
3584 KB |
Output is correct |
27 |
Correct |
12 ms |
3584 KB |
Output is correct |
28 |
Correct |
11 ms |
3968 KB |
Output is correct |
29 |
Correct |
11 ms |
3712 KB |
Output is correct |
30 |
Correct |
11 ms |
3712 KB |
Output is correct |
31 |
Correct |
12 ms |
4352 KB |
Output is correct |
32 |
Correct |
43 ms |
6904 KB |
Output is correct |
33 |
Correct |
41 ms |
6904 KB |
Output is correct |
34 |
Correct |
41 ms |
6904 KB |
Output is correct |
35 |
Runtime error |
9 ms |
5248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
36 |
Halted |
0 ms |
0 KB |
- |