#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5;
int n, u, v, w, dp1[nx], dp2[nx];
vector<pair<int, int>> d[nx];
void dfs(int u, int p, int pw)
{
int sm=0;
vector<pair<int, int>> c;
for (auto [v, w]:d[u]) if (v!=p) dfs(v, u, w), dp1[u]+=dp2[v], sm+=dp2[v], c.push_back({v, w});
for (int i=0; i<c.size(); i++)
{
for (int j=i+1; j<c.size(); j++)
{
dp1[u]=max(dp1[u], sm-dp2[c[i].first]-dp2[c[j].first]+dp1[c[i].first]+dp1[c[j].first]+c[i].second+c[j].second);
}
}
for (int i=0; i<c.size(); i++) dp2[u]=max(dp2[u], sm-dp2[c[i].first]+dp1[c[i].first]+c[i].second+pw);
dp2[u]=max(dp2[u], dp1[u]);
if (u==1&&0)
{
cout<<"debug ";
for (auto x:c) cout<<x.first<<' ';
cout<<'\n';
}
//cout<<"u "<<u<<' '<<dp1[u]<<' '<<dp2[u]<<'\n';
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n;
for (int i=1; i<n; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
dfs(1, 1, 0);
cout<<dp1[1];
}
/*
11 34
35 95
0 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... |