#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<int,int>;
using ll=long long;
const int MX_N = 2e5+5;
const int INF = 2e9+10;
int N;
vector<ii> al[MX_N];
ll f[MX_N][3], g[MX_N][2], ans = 0;
void DFS(int u, int p) {
ll best[] = {-INF,-INF};
for (ii v : al[u]) if (v.first != p) {
DFS(v.first,u);
ll val = max(f[v.first][0], f[v.first][1]+v.second);
f[u][0] += val;
ll x = f[v.first][0]+v.second - val;
FOR(i,0,1) if (x > best[i]) swap(x,best[i]);
}
if (best[0] == -INF) f[u][1] = -INF;
else f[u][1] = f[u][0] + best[0];
if (f[u][1] == -INF || best[1] == -INF) f[u][2] = -INF;
else f[u][2] = f[u][1] + best[1];
ans = max(ans, f[u][0]);
}
void DFS2(int u, int p) {
ll sum = 0;
ll best[] = {-INF,-INF};
ll bestV[] = {-1,-1};
for (ii v : al[u]) if (v.first != p) {
ll val = max(f[v.first][0], f[v.first][1]+v.second);
sum += val;
ll x = f[v.first][0]+v.second - val;
ll y = v.first;
FOR(i,0,1) if (x > best[i]) swap(x,best[i]), swap(y,bestV[i]);
}
for (ii v : al[u]) if (v.first != p) {
ll val = max(f[v.first][0], f[v.first][1]+v.second);
g[v.first][0] = max({
g[u][0] + (sum-val),
v.second + g[u][1] + (sum-val),
v.second + g[u][0] + (sum-val) + (bestV[0] == v.first ? best[1] : best[0])
});
g[v.first][1] = v.second + g[u][0] + (sum-val),
DFS2(v.first,u);
}
ans = max(ans, f[u][0] + g[u][0]);
if (f[u][1] != -INF) ans = max(ans, f[u][1] + g[u][1]);
if (f[u][2] != -INF) ans = max(ans, f[u][2] + g[u][0]);
//TRACE(u _ g[u][0] _ g[u][1]);
//TRACE(u _ f[u][0] _ f[u][1] _ f[u][2] _ g[u][0] _ g[u][1]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
FOR(i,1,N-1){
int A, B, C; cin >> A >> B >> C;
al[A].emplace_back(B,C);
al[B].emplace_back(A,C);
}
DFS(1,0);
g[1][1] = -INF;
DFS2(1,0);
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
4992 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
7 ms |
4992 KB |
Output is correct |
19 |
Correct |
7 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
5120 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
4992 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
7 ms |
4992 KB |
Output is correct |
19 |
Correct |
7 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
5120 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
23 |
Correct |
10 ms |
5504 KB |
Output is correct |
24 |
Correct |
9 ms |
5504 KB |
Output is correct |
25 |
Correct |
10 ms |
5504 KB |
Output is correct |
26 |
Correct |
12 ms |
5888 KB |
Output is correct |
27 |
Correct |
12 ms |
6016 KB |
Output is correct |
28 |
Correct |
13 ms |
6016 KB |
Output is correct |
29 |
Correct |
11 ms |
6016 KB |
Output is correct |
30 |
Correct |
11 ms |
6016 KB |
Output is correct |
31 |
Correct |
12 ms |
6400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
4992 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
7 ms |
4992 KB |
Output is correct |
19 |
Correct |
7 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
5120 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
23 |
Correct |
10 ms |
5504 KB |
Output is correct |
24 |
Correct |
9 ms |
5504 KB |
Output is correct |
25 |
Correct |
10 ms |
5504 KB |
Output is correct |
26 |
Correct |
12 ms |
5888 KB |
Output is correct |
27 |
Correct |
12 ms |
6016 KB |
Output is correct |
28 |
Correct |
13 ms |
6016 KB |
Output is correct |
29 |
Correct |
11 ms |
6016 KB |
Output is correct |
30 |
Correct |
11 ms |
6016 KB |
Output is correct |
31 |
Correct |
12 ms |
6400 KB |
Output is correct |
32 |
Correct |
40 ms |
9600 KB |
Output is correct |
33 |
Correct |
39 ms |
9720 KB |
Output is correct |
34 |
Correct |
44 ms |
9600 KB |
Output is correct |
35 |
Correct |
227 ms |
23800 KB |
Output is correct |
36 |
Correct |
211 ms |
23928 KB |
Output is correct |
37 |
Correct |
205 ms |
23800 KB |
Output is correct |
38 |
Correct |
146 ms |
24292 KB |
Output is correct |
39 |
Correct |
141 ms |
24408 KB |
Output is correct |
40 |
Correct |
146 ms |
24268 KB |
Output is correct |
41 |
Correct |
204 ms |
27760 KB |
Output is correct |