#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+6;
const ll INF=2e15;
ll dp[MAXN][2];
ll dp1[MAXN][3];
vector<pair<ll,ll> >g[MAXN];
ll n;
struct node
{
ll idx;
ll pare;
ll v1,v2,v3;
};
void dfs(int u,int par)
{
vector<node>children;
for(auto v:g[u])
{
if(v.first==par)continue;
dfs(v.first,u);
children.push_back({v.first,v.second,dp[v.first][0],dp[v.first][1]+v.second,dp[v.first][0]+v.second});
}
if(children.size()==0)
{
dp[u][0]=0;
dp[u][1]=-INF;
return;
}
dp1[0][0]=max(children[0].v1,children[0].v2);
dp1[0][1]=children[0].v3;
dp1[0][2]=-INF;
for(int i=1;i<children.size();i++)
{
dp1[i][0]=-INF;
dp1[i][1]=-INF;
dp1[i][2]=-INF;
dp1[i][0]=max(dp1[i][0],dp1[i-1][0]+children[i].v1);
dp1[i][0]=max(dp1[i][0],dp1[i-1][0]+children[i].v2);
dp1[i][1]=max(dp1[i][1],dp1[i-1][1]+children[i].v1);
dp1[i][1]=max(dp1[i][1],dp1[i-1][1]+children[i].v2);
dp1[i][2]=max(dp1[i][2],dp1[i-1][2]+children[i].v1);
dp1[i][2]=max(dp1[i][2],dp1[i-1][2]+children[i].v2);
dp1[i][1]=max(dp1[i][1],dp1[i-1][0]+children[i].v3);
dp1[i][2]=max(dp1[i][2],dp1[i-1][1]+children[i].v3);
}
dp[u][0]=max(dp1[children.size()-1][0],dp1[children.size()-1][2]);
dp[u][1]=dp1[children.size()-1][1];
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
ll x,y,z;
cin>>x>>y>>z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dfs(1,0);
cout<<dp[1][0]<<endl;
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=1;i<children.size();i++)
| ~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
2 ms |
2668 KB |
Output is correct |
6 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
2 ms |
2668 KB |
Output is correct |
6 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
2 ms |
2668 KB |
Output is correct |
6 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
2 ms |
2668 KB |
Output is correct |
6 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |