#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const ll INF = 1e15;
int N;
vector<pii> adj[MAXN+10];
ll dp1[MAXN+10], dp2[MAXN+10], dp3[MAXN+10], dp4[MAXN+10], len[MAXN+10], ans;
void dfs(int now, int bef, int par)
{
ll val=0;
for(pii nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs(nxt.first, now, nxt.second);
dp2[now]+=dp1[nxt.first];
val=max(val, par-dp1[nxt.first]+dp2[nxt.first]+nxt.second);
}
dp1[now]=dp2[now]+val;
}
void dfs2(int now, int bef)
{
ll val=0;
dp4[now]=dp2[bef]-dp1[now]+dp3[bef];
for(pii nxt : adj[bef])
{
if(nxt.first==now) continue;
val=max(val, -dp1[nxt.first]+dp2[nxt.first]+len[nxt.first]+len[now]);
}
dp3[now]=dp2[bef]-dp1[now]+dp3[bef]+val;
dp3[now]=max(dp3[now], dp2[bef]-dp1[now]+dp4[bef]+len[now]+len[bef]);
if(now==1) dp3[now]=dp4[now]=0;
for(pii nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs2(nxt.first, now);
}
//printf("%d %lld %lld %lld %lld\n", now, dp1[now], dp2[now], dp3[now], dp4[now]);
}
int main()
{
int i, j;
scanf("%d", &N);
for(i=1; i<N; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(1, 1, -INF);
dfs2(1, 1);
for(i=1; i<=N; i++) ans=max(ans, dp2[i]+dp3[i]);
printf("%lld", ans);
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:61:15: warning: overflow in implicit constant conversion [-Woverflow]
dfs(1, 1, -INF);
^~~~
beads.cpp:50:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
beads.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
beads.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |