#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int MAXINT = 2e9;
vector<pair<int,int>> graf[MAXN];
int dp[MAXN][2];
pair<int,int> gdz[MAXN][2];
int ans = 0;
int dfs1(int v, int p){
int m = -MAXINT;
for(auto u : graf[v]){
if(u.first == p) continue;
dfs1(u.first, v);
dp[v][0] += max(dp[u.first][0], dp[u.first][1] + u.second);
m = max(m, dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second));
}
dp[v][1] = dp[v][0] + m;
return 0;
}
void dfs2(int v, int p, int k){
int m1, m2;
int k1, k2;
m1 = m2 = k1 = k2 = -MAXINT;
if(v != 1){
int w1, w2;
w1 = dp[p][0] - max(dp[v][0], dp[v][1] + k);
if(gdz[p][0].first == v){
w2 = w1 + gdz[p][1].second;
}
else{
w2 = w1 + gdz[p][0].second;
}
int ma = w1 + k - max(w1, w2 + k);
for(auto u : graf[v]){
if(u.first == p) continue;
ma = max(ma, dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second));
}
m1 = w1 + k - max(w1, w2 + k);
k1 = p;
dp[v][0] += max(w1, w2 + k);
dp[v][1] += max(w1, w2 + k) + ma;
}
for(auto u : graf[v]){
if(u.first == p) continue;
int c = dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second);
if(c > m1){
m2 = m1;
m1 = c;
k2 = k1;
k1 = u.first;
}
else if(c > m2){
m2 = c;
k2 = u.first;
}
}
ans = max(ans, dp[v][0]);
gdz[v][0] = {k1, m1};
gdz[v][1] = {k2, m2};
for(auto u : graf[v]){
if(u.first == p) continue;
dfs2(u.first, v, u.second);
}
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int a, b, c;
for(int i = 0; i < n-1; ++i){
cin >> a >> b >> c;
graf[a].push_back({b,c});
graf[b].push_back({a,c});
}
dfs1(1, -1);
ans = dp[1][0];
dfs2(1, -1, 0);
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |