#include <bits/stdc++.h>
using namespace std;
const int NMAX = 200000 + 5;
const int INF = 2E9 + 15;
int N;
vector <pair <int, int> > graph[NMAX];
int fatherEdgeCost[NMAX];
int dp[NMAX][2];
void dfs1(int node, int father) {
dp[node][0] = 0;
dp[node][1] = -INF;
for (auto it: graph[node])
if (it.first != father) {
dfs1(it.first, node);
int val = max(dp[it.first][0], dp[it.first][1] + it.second);
dp[node][0] += val;
dp[node][1] = max(dp[node][1], it.second + dp[it.first][0] - val);
}
dp[node][1] = dp[node][0] + dp[node][1];
}
int ans;
int getBestNotNode(const vector <pair <int, int> > &v, int node) {
for (int i = 0; i < v.size(); ++ i)
if (v[i].second != node)
return v[i].first;
return -INF;
}
int up[NMAX][2];
void dfs2(int node, int father, int edge) {
int cost = dp[node][0] + max(up[node][0], up[node][1] + edge);
ans = max(ans, cost);
vector <pair <int, int> > v;
if (father)
v.push_back(make_pair(up[node][0] + edge - max(up[node][0], up[node][1] + edge), father));
for (auto it: graph[node])
if (it.first != father) {
int val = max(dp[it.first][0], dp[it.first][1] + it.second);
up[it.first][0] = dp[node][0] - val + max(up[node][0], up[node][1] + edge);
v.push_back(make_pair(it.second + dp[it.first][0] - val, it.first));
}
sort(v.begin(), v.end(), greater <pair <int, int> >());
if (v.size() > 2)
v.resize(2);
for (auto it: graph[node])
if (it.first != father) {
int val = max(dp[it.first][0], dp[it.first][1] + it.second);
up[it.first][1] = cost + getBestNotNode(v, it.first) - val;
}
for (auto it: graph[node])
if (it.first != father)
dfs2(it.first, node, it.second);
}
int main()
{
//freopen("data.in", "r", stdin);
cin >> N;
for (int i = 1; i < N; ++ i) {
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back({b, c});
graph[b].push_back({a, c});
}
dfs1(1, 0);
dfs2(1, 0, 0);
cout << ans << '\n';
return 0;
}
Compilation message
beads.cpp: In function 'int getBestNotNode(const std::vector<std::pair<int, int> >&, int)':
beads.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); ++ i)
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 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 |
6 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 |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 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 |
6 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 |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
5120 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 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 |
6 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 |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
5120 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
23 |
Correct |
12 ms |
5376 KB |
Output is correct |
24 |
Correct |
12 ms |
5376 KB |
Output is correct |
25 |
Correct |
11 ms |
5244 KB |
Output is correct |
26 |
Correct |
18 ms |
5564 KB |
Output is correct |
27 |
Correct |
17 ms |
5632 KB |
Output is correct |
28 |
Correct |
20 ms |
5760 KB |
Output is correct |
29 |
Correct |
17 ms |
5752 KB |
Output is correct |
30 |
Correct |
18 ms |
5632 KB |
Output is correct |
31 |
Correct |
18 ms |
6272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 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 |
6 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 |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
5120 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
23 |
Correct |
12 ms |
5376 KB |
Output is correct |
24 |
Correct |
12 ms |
5376 KB |
Output is correct |
25 |
Correct |
11 ms |
5244 KB |
Output is correct |
26 |
Correct |
18 ms |
5564 KB |
Output is correct |
27 |
Correct |
17 ms |
5632 KB |
Output is correct |
28 |
Correct |
20 ms |
5760 KB |
Output is correct |
29 |
Correct |
17 ms |
5752 KB |
Output is correct |
30 |
Correct |
18 ms |
5632 KB |
Output is correct |
31 |
Correct |
18 ms |
6272 KB |
Output is correct |
32 |
Correct |
83 ms |
7692 KB |
Output is correct |
33 |
Correct |
81 ms |
7928 KB |
Output is correct |
34 |
Correct |
80 ms |
7672 KB |
Output is correct |
35 |
Correct |
444 ms |
15600 KB |
Output is correct |
36 |
Correct |
433 ms |
15660 KB |
Output is correct |
37 |
Correct |
456 ms |
15700 KB |
Output is correct |
38 |
Correct |
333 ms |
19072 KB |
Output is correct |
39 |
Correct |
339 ms |
18404 KB |
Output is correct |
40 |
Correct |
345 ms |
17624 KB |
Output is correct |
41 |
Correct |
455 ms |
23140 KB |
Output is correct |