#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define int long long
const int N = 2e5 + 1;
typedef pair<int,int> ii;
vector<ii> g[N];
int f[N][2];
void dfs(int u,int p) {
int mx1 = -1e9;
int mx2 = -1e9;
f[u][0] = 0;
for(ii e : g[u]) {
int v = e.first;
int c = e.second;
if (v == p) continue;
dfs(v,u);
f[u][0] += max(f[v][1] + c,f[v][0]);
if (mx2 < min(c,f[v][0] - f[v][1]))
mx2 = min(c,f[v][0] - f[v][1]);
if (mx1 < mx2)
swap(mx1,mx2);
}
f[u][1] = f[u][0] + mx1;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
for(int i = 1 ; i < n ; ++i) {
int x; cin >> x;
int y; cin >> y;
int c; cin >> c;
g[x].pb(y,c);
g[y].pb(x,c);
}
int ans = 0;
for(int i = 1 ; i <= n ; ++i) {
dfs(i,0);
ans = max(ans,f[i][0]);
}
cout << ans << endl;
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
6 ms |
4984 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
7 ms |
5076 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
6 ms |
4984 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
7 ms |
5076 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
7 ms |
5112 KB |
Output is correct |
14 |
Correct |
7 ms |
5112 KB |
Output is correct |
15 |
Correct |
6 ms |
4984 KB |
Output is correct |
16 |
Correct |
7 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5112 KB |
Output is correct |
18 |
Correct |
7 ms |
5112 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
7 ms |
4984 KB |
Output is correct |
21 |
Correct |
7 ms |
5112 KB |
Output is correct |
22 |
Correct |
7 ms |
5112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
6 ms |
4984 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
7 ms |
5076 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
7 ms |
5112 KB |
Output is correct |
14 |
Correct |
7 ms |
5112 KB |
Output is correct |
15 |
Correct |
6 ms |
4984 KB |
Output is correct |
16 |
Correct |
7 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5112 KB |
Output is correct |
18 |
Correct |
7 ms |
5112 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
7 ms |
4984 KB |
Output is correct |
21 |
Correct |
7 ms |
5112 KB |
Output is correct |
22 |
Correct |
7 ms |
5112 KB |
Output is correct |
23 |
Execution timed out |
1073 ms |
5624 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Correct |
6 ms |
4984 KB |
Output is correct |
5 |
Correct |
6 ms |
4984 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
7 ms |
5076 KB |
Output is correct |
9 |
Correct |
6 ms |
4984 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
7 ms |
5112 KB |
Output is correct |
14 |
Correct |
7 ms |
5112 KB |
Output is correct |
15 |
Correct |
6 ms |
4984 KB |
Output is correct |
16 |
Correct |
7 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5112 KB |
Output is correct |
18 |
Correct |
7 ms |
5112 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
7 ms |
4984 KB |
Output is correct |
21 |
Correct |
7 ms |
5112 KB |
Output is correct |
22 |
Correct |
7 ms |
5112 KB |
Output is correct |
23 |
Execution timed out |
1073 ms |
5624 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |