#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int N = 2e5 + 5;
int n, dp[N][2], ans, g[N][2], cnt[N];
vector<ii> a[N], b[N];
vector<int> l[N], r[N], sax[2][N], cax[2][N];
void dfs(int u, int p) {
dp[u][0] = dp[u][1] = 0;
cnt[u] = 0;
for(int i = 0; i < a[u].size(); ++i) {
int v = a[u][i].first;
if(v == p) continue;
dfs(v, u);
cnt[u]++; b[u][cnt[u]] = a[u][i];
}
l[u][0] = 0;
for(int i = 1; i <= cnt[u]; ++i) {
int v = b[u][i].first, w = b[u][i].second;
l[u][i] = l[u][i - 1] + max(dp[v][1] + w, dp[v][0]);
}
r[u][cnt[u] + 1] = 0;
for(int i = cnt[u]; i >= 1; --i) {
int v = b[u][i].first, w = b[u][i].second;
r[u][i] = r[u][i + 1] + max(dp[v][1] + w, dp[v][0]);
}
dp[u][0] = l[u][cnt[u]];
for(int i = 1; i <= cnt[u]; ++i) {
int v = b[u][i].first, w = b[u][i].second;
dp[u][1] = max(dp[u][1], l[u][i - 1] + r[u][i + 1] + dp[v][0] + w);
}
if(a[u].size() == 1) dp[u][1] = -1e9;
}
void redfs(int u, int p) {
if(a[p].size() == 1) g[p][1] = -1e9;
sax[1][u][0] = -1e9;
for(int i = 1; i <= cnt[u]; ++i) {
int v = b[u][i].first, w = b[u][i].second;
sax[0][u][i] = sax[0][u][i - 1] + max(dp[v][1] + w, dp[v][0]);
sax[1][u][i] = sax[0][u][i - 1] + w + dp[v][0];
sax[1][u][i] = max(sax[1][u][i], sax[1][u][i - 1] + max(dp[v][1] + w, dp[v][0]));
}
int W = 0;
for(int i = 0; i < a[u].size(); ++i) if(a[u][i].first == p) W = a[u][i].second;
if(u != 1) {
cax[0][u][cnt[u] + 1] = max(g[p][1] + W, g[p][0]);
cax[1][u][cnt[u] + 1] = W + g[p][0];
}
else cax[0][u][cnt[u] + 1] = 0, cax[1][u][cnt[u] + 1] = -1e9;
for(int i = cnt[u]; i >= 1; --i) {
int v = b[u][i].first, w = b[u][i].second;
cax[0][u][i] = cax[0][u][i + 1] + max(dp[v][1] + w, dp[v][0]);
cax[1][u][i] = cax[0][u][i + 1] + w + dp[v][0];
cax[1][u][i] = max(cax[1][u][i], cax[1][u][i + 1] + max(dp[v][1] + w, dp[v][0]));
}
ans = max(ans, cax[0][u][1]);
for(int i = 1; i <= cnt[u]; ++i) {
int v = b[u][i].first;
g[u][0] = sax[0][u][i - 1] + cax[0][u][i + 1];
g[u][1] = max(sax[1][u][i - 1] + cax[0][u][i + 1], sax[0][u][i - 1] + cax[1][u][i + 1]);
redfs(v, u);
}
}
void get(int &x) {
x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while('0' <= c && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
}
int main() {
get(n);
for(int i = 1; i < n; ++i) {
int u, v, w;
get(u); get(v); get(w);
a[u].push_back(ii(v, w));
a[v].push_back(ii(u, w));
}
for(int i = 1; i <= n; ++i) l[i].assign(a[i].size() + 3, 0), r[i].assign(a[i].size() + 3, 0), b[i].assign(a[i].size() + 3, ii(0, 0)), sax[0][i].assign(a[i].size() + 3, 0), sax[1][i].assign(a[i].size() + 3, 0), cax[0][i].assign(a[i].size() + 3, 0), cax[1][i].assign(a[i].size() + 3, 0);
dfs(1, 1);
redfs(1, 1);
cout << ans;
}
Compilation message
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:15:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a[u].size(); ++i) {
~~^~~~~~~~~~~~~
beads.cpp: In function 'void redfs(int, int)':
beads.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a[u].size(); ++i) if(a[u][i].first == p) W = a[u][i].second;
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
38008 KB |
Output is correct |
2 |
Correct |
33 ms |
37880 KB |
Output is correct |
3 |
Correct |
34 ms |
37908 KB |
Output is correct |
4 |
Correct |
34 ms |
37888 KB |
Output is correct |
5 |
Correct |
35 ms |
38008 KB |
Output is correct |
6 |
Correct |
35 ms |
37888 KB |
Output is correct |
7 |
Correct |
35 ms |
37888 KB |
Output is correct |
8 |
Correct |
36 ms |
37888 KB |
Output is correct |
9 |
Correct |
36 ms |
37880 KB |
Output is correct |
10 |
Correct |
37 ms |
37880 KB |
Output is correct |
11 |
Correct |
35 ms |
38016 KB |
Output is correct |
12 |
Correct |
36 ms |
37888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
38008 KB |
Output is correct |
2 |
Correct |
33 ms |
37880 KB |
Output is correct |
3 |
Correct |
34 ms |
37908 KB |
Output is correct |
4 |
Correct |
34 ms |
37888 KB |
Output is correct |
5 |
Correct |
35 ms |
38008 KB |
Output is correct |
6 |
Correct |
35 ms |
37888 KB |
Output is correct |
7 |
Correct |
35 ms |
37888 KB |
Output is correct |
8 |
Correct |
36 ms |
37888 KB |
Output is correct |
9 |
Correct |
36 ms |
37880 KB |
Output is correct |
10 |
Correct |
37 ms |
37880 KB |
Output is correct |
11 |
Correct |
35 ms |
38016 KB |
Output is correct |
12 |
Correct |
36 ms |
37888 KB |
Output is correct |
13 |
Correct |
36 ms |
37884 KB |
Output is correct |
14 |
Correct |
36 ms |
37888 KB |
Output is correct |
15 |
Correct |
35 ms |
38008 KB |
Output is correct |
16 |
Correct |
37 ms |
38016 KB |
Output is correct |
17 |
Correct |
35 ms |
38008 KB |
Output is correct |
18 |
Correct |
36 ms |
38016 KB |
Output is correct |
19 |
Correct |
36 ms |
38008 KB |
Output is correct |
20 |
Correct |
36 ms |
38016 KB |
Output is correct |
21 |
Correct |
36 ms |
38008 KB |
Output is correct |
22 |
Correct |
33 ms |
38016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
38008 KB |
Output is correct |
2 |
Correct |
33 ms |
37880 KB |
Output is correct |
3 |
Correct |
34 ms |
37908 KB |
Output is correct |
4 |
Correct |
34 ms |
37888 KB |
Output is correct |
5 |
Correct |
35 ms |
38008 KB |
Output is correct |
6 |
Correct |
35 ms |
37888 KB |
Output is correct |
7 |
Correct |
35 ms |
37888 KB |
Output is correct |
8 |
Correct |
36 ms |
37888 KB |
Output is correct |
9 |
Correct |
36 ms |
37880 KB |
Output is correct |
10 |
Correct |
37 ms |
37880 KB |
Output is correct |
11 |
Correct |
35 ms |
38016 KB |
Output is correct |
12 |
Correct |
36 ms |
37888 KB |
Output is correct |
13 |
Correct |
36 ms |
37884 KB |
Output is correct |
14 |
Correct |
36 ms |
37888 KB |
Output is correct |
15 |
Correct |
35 ms |
38008 KB |
Output is correct |
16 |
Correct |
37 ms |
38016 KB |
Output is correct |
17 |
Correct |
35 ms |
38008 KB |
Output is correct |
18 |
Correct |
36 ms |
38016 KB |
Output is correct |
19 |
Correct |
36 ms |
38008 KB |
Output is correct |
20 |
Correct |
36 ms |
38016 KB |
Output is correct |
21 |
Correct |
36 ms |
38008 KB |
Output is correct |
22 |
Correct |
33 ms |
38016 KB |
Output is correct |
23 |
Correct |
41 ms |
39416 KB |
Output is correct |
24 |
Correct |
63 ms |
39428 KB |
Output is correct |
25 |
Correct |
41 ms |
39416 KB |
Output is correct |
26 |
Correct |
48 ms |
41080 KB |
Output is correct |
27 |
Correct |
51 ms |
41080 KB |
Output is correct |
28 |
Correct |
48 ms |
41120 KB |
Output is correct |
29 |
Correct |
50 ms |
41136 KB |
Output is correct |
30 |
Correct |
46 ms |
41080 KB |
Output is correct |
31 |
Correct |
46 ms |
41336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
38008 KB |
Output is correct |
2 |
Correct |
33 ms |
37880 KB |
Output is correct |
3 |
Correct |
34 ms |
37908 KB |
Output is correct |
4 |
Correct |
34 ms |
37888 KB |
Output is correct |
5 |
Correct |
35 ms |
38008 KB |
Output is correct |
6 |
Correct |
35 ms |
37888 KB |
Output is correct |
7 |
Correct |
35 ms |
37888 KB |
Output is correct |
8 |
Correct |
36 ms |
37888 KB |
Output is correct |
9 |
Correct |
36 ms |
37880 KB |
Output is correct |
10 |
Correct |
37 ms |
37880 KB |
Output is correct |
11 |
Correct |
35 ms |
38016 KB |
Output is correct |
12 |
Correct |
36 ms |
37888 KB |
Output is correct |
13 |
Correct |
36 ms |
37884 KB |
Output is correct |
14 |
Correct |
36 ms |
37888 KB |
Output is correct |
15 |
Correct |
35 ms |
38008 KB |
Output is correct |
16 |
Correct |
37 ms |
38016 KB |
Output is correct |
17 |
Correct |
35 ms |
38008 KB |
Output is correct |
18 |
Correct |
36 ms |
38016 KB |
Output is correct |
19 |
Correct |
36 ms |
38008 KB |
Output is correct |
20 |
Correct |
36 ms |
38016 KB |
Output is correct |
21 |
Correct |
36 ms |
38008 KB |
Output is correct |
22 |
Correct |
33 ms |
38016 KB |
Output is correct |
23 |
Correct |
41 ms |
39416 KB |
Output is correct |
24 |
Correct |
63 ms |
39428 KB |
Output is correct |
25 |
Correct |
41 ms |
39416 KB |
Output is correct |
26 |
Correct |
48 ms |
41080 KB |
Output is correct |
27 |
Correct |
51 ms |
41080 KB |
Output is correct |
28 |
Correct |
48 ms |
41120 KB |
Output is correct |
29 |
Correct |
50 ms |
41136 KB |
Output is correct |
30 |
Correct |
46 ms |
41080 KB |
Output is correct |
31 |
Correct |
46 ms |
41336 KB |
Output is correct |
32 |
Correct |
143 ms |
53388 KB |
Output is correct |
33 |
Correct |
148 ms |
53368 KB |
Output is correct |
34 |
Correct |
133 ms |
53368 KB |
Output is correct |
35 |
Correct |
645 ms |
99896 KB |
Output is correct |
36 |
Correct |
652 ms |
99960 KB |
Output is correct |
37 |
Correct |
649 ms |
99828 KB |
Output is correct |
38 |
Correct |
564 ms |
102784 KB |
Output is correct |
39 |
Correct |
562 ms |
101332 KB |
Output is correct |
40 |
Correct |
793 ms |
102184 KB |
Output is correct |
41 |
Correct |
697 ms |
103284 KB |
Output is correct |