// fest
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)
typedef long long ll;
typedef long double ld;
using namespace std;
void FREOPEN() {
#ifdef COMP
freopen(".in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
}
inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }
const int N = 200500, inf = 1e9 * 2, MOD = (int)1e9 + 7;
char CH[N];
const ll INF = 1e18;
const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};
int dp[N][2];
vector<pair<int, int> > g[N];
pair<int, int> opt[N];
int ans;
void dfs(int v, int pr, int last) {
dp[v][0] = 0;
dp[v][1] = -inf;
for (auto i : g[v]) {
int u = i.F;
int c = i.S;
if (u == pr) continue;
dfs(u, v, c);
dp[v][0] += max(dp[u][0], dp[u][1]);
}
for (auto i : g[v]) {
int u = i.F;
int c = i.S;
if (u == pr) continue;
if (dp[v][1] < last + (dp[v][0] - max(dp[u][0], dp[u][1])) + c + dp[u][0]) {
dp[v][1] = last + (dp[v][0] - max(dp[u][0], dp[u][1])) + c + dp[u][0];
opt[v] = {u, c};
}
}
}
void calc(int v, int pr, int last, int dp0, int dp1) {
ans = max(ans, dp[v][0] + max(dp0, dp1));
for (auto i : g[v]) {
int u = i.F;
int c = i.S;
if (u == pr) continue;
int go0 = dp[v][0] - max(dp[u][0], dp[u][1]) + max(dp0, dp1);
int go1 = -inf;
if (last) go1 = go0 - max(dp0, dp1) + last + dp0 + c;
if (opt[v].F != u) {
go1 = max(go1, go0 - max(dp[opt[v].F][0], dp[opt[v].F][1]) + opt[v].S + c + dp[opt[v].F][0]);
}
else {
for (auto j : g[v]) {
int u2 = j.F;
int c2 = j.S;
if (u2 == pr || u2 == u) continue;
go1 = max(go1, go0 - max(dp[u2][0], dp[u2][1]) + c2 + c + dp[u2][0]);
}
}
calc(u, v, c, go0, go1);
}
}
int main() {
FREOPEN();
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
int x, y, c;
scanf("%d %d %d", &x, &y, &c);
g[x].pb({y, c});
g[y].pb({x, c});
}
dfs(1, 0, 0);
calc(1, 0, 0, 0, -inf);
cout << ans;
return 0;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &x, &y, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
5120 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 |
6 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 |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
5120 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 |
6 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 |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 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 |
6 ms |
4992 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 |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
5120 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 |
6 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 |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 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 |
6 ms |
4992 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 |
9 ms |
5388 KB |
Output is correct |
24 |
Correct |
9 ms |
5376 KB |
Output is correct |
25 |
Correct |
8 ms |
5248 KB |
Output is correct |
26 |
Correct |
11 ms |
5504 KB |
Output is correct |
27 |
Correct |
13 ms |
5632 KB |
Output is correct |
28 |
Correct |
11 ms |
5760 KB |
Output is correct |
29 |
Correct |
12 ms |
5504 KB |
Output is correct |
30 |
Correct |
11 ms |
5632 KB |
Output is correct |
31 |
Correct |
12 ms |
5888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
5120 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 |
6 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 |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 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 |
6 ms |
4992 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 |
9 ms |
5388 KB |
Output is correct |
24 |
Correct |
9 ms |
5376 KB |
Output is correct |
25 |
Correct |
8 ms |
5248 KB |
Output is correct |
26 |
Correct |
11 ms |
5504 KB |
Output is correct |
27 |
Correct |
13 ms |
5632 KB |
Output is correct |
28 |
Correct |
11 ms |
5760 KB |
Output is correct |
29 |
Correct |
12 ms |
5504 KB |
Output is correct |
30 |
Correct |
11 ms |
5632 KB |
Output is correct |
31 |
Correct |
12 ms |
5888 KB |
Output is correct |
32 |
Correct |
44 ms |
7672 KB |
Output is correct |
33 |
Correct |
42 ms |
7672 KB |
Output is correct |
34 |
Correct |
39 ms |
7644 KB |
Output is correct |
35 |
Correct |
243 ms |
15672 KB |
Output is correct |
36 |
Correct |
259 ms |
15720 KB |
Output is correct |
37 |
Correct |
255 ms |
15716 KB |
Output is correct |
38 |
Correct |
168 ms |
15972 KB |
Output is correct |
39 |
Correct |
134 ms |
14420 KB |
Output is correct |
40 |
Correct |
168 ms |
15872 KB |
Output is correct |
41 |
Correct |
235 ms |
19676 KB |
Output is correct |