#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
const int maxn = 2e5 + 10;
vector <pii> adj[maxn];
ll dp[5][maxn];
int inf = 1e9;
//dp[0][u] = max gain age u too hish gilasi vasat nabashe!
//dp[1][u] = max gain age u bein pedar o yeki az bache hash bashe
//dp[2][u] = max gain age u bein do ta az bache hash bashe
//ans = max(dp[0 , 2][0]) !
void dfs(int u, int p = -1){
int mx1 = -inf, mx2 = -inf;
for(auto i : adj[u]){
int v = i.F;
if(v != p){
dfs(v, u);
if(dp[1][v])
dp[1][v] += i.S;
dp[0][u] += dp[1][v];
int x = max(dp[0][v], dp[2][v]);
x += i.S;
if(mx1 < (x - dp[1][v])){
mx2 = mx1;
mx1 = (x - dp[1][v]);
}else if(mx2 < (x - dp[1][v])){
mx2 = (x - dp[1][v]);
}
}
}
dp[1][u] = dp[2][u] = dp[0][u];
dp[1][u] = (adj[u].size() > 1 || u == 0) ? dp[1][u] + mx1 : 0;
dp[2][u] += (((int)adj[u].size() > 2) || (u == 0 && (int)adj[u].size() > 1)) ? mx2 + mx1 : 0;
// cout << u + 1 << " " << dp[0][u] << " " << dp[1][u] << " " << dp[2][u] << " | " << mx1 << " " << mx2 << " !!! " << endl;
}
int main(){
fast_io;
int n;
cin >> n;
for(int i = 0; i < n - 1; i ++){
int a, b, c;
cin >> a >> b >> c;
a --; b --;
adj[a].pb({b, c});
adj[b].pb({a, c});
}
dfs(0);
cout << max({dp[0][0], dp[2][0]});
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
3 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
3 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
3 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
3 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |