#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define INF 1000000000000000000
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair< ll, ll > pll;
typedef vector< ll > vl;
typedef vector< pll > vll;
ll n;
vll grafo[N];
ll dp[N][2];
// 0: aresta do pai não foi pega
// 1: aresta do pai já foi pega
void DFS(ll u, ll pai, ll wpai)
{
ll sum, a, b;
sum = 0;
a = -INF;
for(auto [v, w] : grafo[u])
{
if(v == pai) continue;
DFS(v, u, w);
sum += dp[v][0];
a = max(a, (dp[v][1] + w) - dp[v][0]);
}
dp[u][1] = sum;
dp[u][0] = dp[u][1];
dp[u][0] = max(dp[u][0], sum + a + wpai);
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll u, v, w, i;
cin >> n;
for(i = 1; i < n; i++)
{
cin >> u >> v >> w;
grafo[u].pb({v, w});
grafo[v].pb({u, w});
}
ll x = 0;
DFS(1, 1, -INF);
x = dp[1][1];
for(i = 1; i <= n; i++)
{
DFS(i, i, -INF);
x = max(x, dp[i][1]);
}
cout << x << endl;
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... |