/*input
5
1 2 10
1 3 40
1 4 15
1 5 20
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 200007;
int dp[N][2], par[N], n, ans;
vector<pair<int, int> > child[N];
void dfs(int u){
for(auto v:child[u]){
if(v.first == par[u]) continue;
par[v.first] = u;
dfs(v.first);
dp[u][0] += max(dp[v.first][0], dp[v.first][1] + v.second);
}
for(auto v:child[u])
if(v.first != par[u])
dp[u][1] = max(dp[u][1], dp[u][0] + dp[v.first][0] + v.second - max(dp[v.first][0], dp[v.first][1] + v.second));
}
int main(){
cin >> n;
for(int i = 1; i < n; ++i){
int u, v, w; cin >> u >> v >> w;
child[u].push_back({v, w});
child[v].push_back({u, w});
}
for(int i = 1; i <= n; ++i){
memset(par, 0, sizeof par);
memset(dp, 0, sizeof dp);
for(int j = 1; j <= n; ++j)
dp[j][1] = INT_MIN;
dfs(i);
ans = max(ans, dp[i][0]);
}
cout << ans << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
9 ms |
7424 KB |
Output is correct |
3 |
Correct |
9 ms |
7424 KB |
Output is correct |
4 |
Correct |
8 ms |
7424 KB |
Output is correct |
5 |
Correct |
9 ms |
7424 KB |
Output is correct |
6 |
Correct |
9 ms |
7424 KB |
Output is correct |
7 |
Correct |
8 ms |
7424 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
9 ms |
7424 KB |
Output is correct |
11 |
Correct |
9 ms |
7424 KB |
Output is correct |
12 |
Correct |
8 ms |
7424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
9 ms |
7424 KB |
Output is correct |
3 |
Correct |
9 ms |
7424 KB |
Output is correct |
4 |
Correct |
8 ms |
7424 KB |
Output is correct |
5 |
Correct |
9 ms |
7424 KB |
Output is correct |
6 |
Correct |
9 ms |
7424 KB |
Output is correct |
7 |
Correct |
8 ms |
7424 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
9 ms |
7424 KB |
Output is correct |
11 |
Correct |
9 ms |
7424 KB |
Output is correct |
12 |
Correct |
8 ms |
7424 KB |
Output is correct |
13 |
Correct |
19 ms |
7360 KB |
Output is correct |
14 |
Correct |
21 ms |
7396 KB |
Output is correct |
15 |
Correct |
19 ms |
7424 KB |
Output is correct |
16 |
Correct |
29 ms |
7424 KB |
Output is correct |
17 |
Correct |
30 ms |
7352 KB |
Output is correct |
18 |
Correct |
31 ms |
7296 KB |
Output is correct |
19 |
Correct |
31 ms |
7416 KB |
Output is correct |
20 |
Correct |
30 ms |
7424 KB |
Output is correct |
21 |
Correct |
29 ms |
7424 KB |
Output is correct |
22 |
Correct |
31 ms |
7424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
9 ms |
7424 KB |
Output is correct |
3 |
Correct |
9 ms |
7424 KB |
Output is correct |
4 |
Correct |
8 ms |
7424 KB |
Output is correct |
5 |
Correct |
9 ms |
7424 KB |
Output is correct |
6 |
Correct |
9 ms |
7424 KB |
Output is correct |
7 |
Correct |
8 ms |
7424 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
9 ms |
7424 KB |
Output is correct |
11 |
Correct |
9 ms |
7424 KB |
Output is correct |
12 |
Correct |
8 ms |
7424 KB |
Output is correct |
13 |
Correct |
19 ms |
7360 KB |
Output is correct |
14 |
Correct |
21 ms |
7396 KB |
Output is correct |
15 |
Correct |
19 ms |
7424 KB |
Output is correct |
16 |
Correct |
29 ms |
7424 KB |
Output is correct |
17 |
Correct |
30 ms |
7352 KB |
Output is correct |
18 |
Correct |
31 ms |
7296 KB |
Output is correct |
19 |
Correct |
31 ms |
7416 KB |
Output is correct |
20 |
Correct |
30 ms |
7424 KB |
Output is correct |
21 |
Correct |
29 ms |
7424 KB |
Output is correct |
22 |
Correct |
31 ms |
7424 KB |
Output is correct |
23 |
Execution timed out |
1060 ms |
7552 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
9 ms |
7424 KB |
Output is correct |
3 |
Correct |
9 ms |
7424 KB |
Output is correct |
4 |
Correct |
8 ms |
7424 KB |
Output is correct |
5 |
Correct |
9 ms |
7424 KB |
Output is correct |
6 |
Correct |
9 ms |
7424 KB |
Output is correct |
7 |
Correct |
8 ms |
7424 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
9 ms |
7424 KB |
Output is correct |
11 |
Correct |
9 ms |
7424 KB |
Output is correct |
12 |
Correct |
8 ms |
7424 KB |
Output is correct |
13 |
Correct |
19 ms |
7360 KB |
Output is correct |
14 |
Correct |
21 ms |
7396 KB |
Output is correct |
15 |
Correct |
19 ms |
7424 KB |
Output is correct |
16 |
Correct |
29 ms |
7424 KB |
Output is correct |
17 |
Correct |
30 ms |
7352 KB |
Output is correct |
18 |
Correct |
31 ms |
7296 KB |
Output is correct |
19 |
Correct |
31 ms |
7416 KB |
Output is correct |
20 |
Correct |
30 ms |
7424 KB |
Output is correct |
21 |
Correct |
29 ms |
7424 KB |
Output is correct |
22 |
Correct |
31 ms |
7424 KB |
Output is correct |
23 |
Execution timed out |
1060 ms |
7552 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |