이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll dp[maxN][2];
vector<pli>g[maxN];
ll w[maxN];
void dfs(ll u,ll p)
{
dp[u][0]=0;
dp[u][1]=-inf;
vector<ll>vec;
for(auto zz:g[u])
{
if(zz.fi==p) continue;
w[zz.fi]=zz.se;
dfs(zz.fi,u);
dp[u][0]+=max(dp[zz.fi][0],dp[zz.fi][1]);
vec.pb(-max(dp[zz.fi][0],dp[zz.fi][1])+dp[zz.fi][0]+zz.se);
}
sort(vec.begin(),vec.end(),greater<ll>());
ll x=dp[u][0];
if(vec.size()>=2)
{
dp[u][0]=max(dp[u][0],x+vec[0]+vec[1]);
}
if(vec.size()>=1) dp[u][1]=max(dp[u][1],x+vec[0]+w[u]);
vec.clear();
}
ll u,v,c,n;
void solve()
{
cin >> n;
for(int i=1;i<n;i++)
{
cin >>u >> v >> c;
g[u].pb({v,c});
g[v].pb({u,c});
}
ll ans=0;
for(int i=1;i<=n;i++)
{
dfs(u,0);
ans=max(ans,dp[u][0]);
}
cout << ans;
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
# | 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... |