This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int N = 333333;
vector<ii> adj[N];
int dp[N][2];
const int INF = int(1e9);
void dfs(int u, int p)
{
vi pre(2,-INF); pre[0]=0;
dp[u][0]=dp[u][1]=-INF;
for(ii X:adj[u])
{
int v=X.fi; int w=X.se;
if(v==p) continue;
dfs(v,u);
vi nw(2,-INF);
nw[0]=max(nw[0],pre[0]+dp[v][0]);
nw[1]=max(nw[1],pre[1]+dp[v][0]);
nw[0]=max(nw[0],pre[0]+w+dp[v][1]);
nw[1]=max(nw[1],pre[0]+w+dp[v][0]);
nw[1]=max(nw[1],pre[1]+w+dp[v][1]);
pre=nw;
}
dp[u][0]=pre[0]; dp[u][1]=pre[1];
//cerr<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=0;i<n-1;i++)
{
int u,v; cin>>u>>v; u--; v--;
int w; cin>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
int ans=0;
for(int i=0;i<n;i++)
{
dfs(i,-1);
ans=max(ans,dp[i][0]);
}
cout<<ans<<'\n';
}
# | 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... |