#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=2e15;
ll par[MAXN],n;
vector<pair<ll,ll> >g[MAXN];
set<pair<ll,ll> >dp1[MAXN];
map<ll,ll>mp1[MAXN];
//map<ll,ll>mp0[MAXN];
set<pair<ll,ll> >dp0[MAXN];
ll dp0v[MAXN];
ll root;
ll getdp1v(ll u)
{
if(dp1[u].size()==0)return -INF;
return dp0v[u]-(*dp1[u].begin()).first;
}
struct save1
{
ll what,where,w0,w1;
};
struct save2
{
ll mx,what,where,weight,dp0vwhat;
};
stack<save1>st1;
stack<save2>st2;
void remove(ll what,ll where)
{
ll w0=dp0v[what];
dp0v[where]-=w0;
dp0[where].erase({w0,what});
ll w1=mp1[where][what];
dp1[where].erase({w1,what});
st1.push({what,where,w0,w1});
}
void rollback1()
{
save1 xd=st1.top();
st1.pop();
dp0v[xd.where]+=xd.w0;
dp0[xd.where].insert({xd.w0,xd.what});
dp1[xd.where].insert({xd.w1,xd.what});
}
void add(ll what,ll where,ll weight)
{
ll mx=max(dp0v[what],getdp1v(what)+weight);
dp0[where].insert({mx,what});
dp0v[where]+=mx;
dp1[where].insert({mx-dp0v[what]-weight,what});
st2.push({mx,what,where,weight,dp0v[what]});
}
void rollback2()
{
save2 xd=st2.top();st2.pop();
dp0[xd.where].erase({xd.mx,xd.what});
dp0v[xd.where]-=xd.mx;
dp1[xd.where].erase({xd.mx-xd.dp0vwhat-xd.weight,xd.what});
}
void dfs(ll u,ll p)
{
par[u]=p;
vector<pair<pair<ll,ll>,ll> >ch;
vector<ll>ch1;
for(auto v:g[u])
{
if(v.first==p)continue;
dfs(v.first,u);
ch.push_back({{dp0v[v.first],getdp1v(v.first)},v.second});
ch1.push_back(v.first);
}
for(ll i=0;i<ch.size();++i)
{
dp0v[u]+=max(ch[i].first.first,ch[i].first.second+ch[i].second);
dp0[u].insert({max(ch[i].first.first,ch[i].first.second+ch[i].second),ch1[i]});
//mp0[u][ch1[i]]=max(ch[i].first.first,ch[i].first.second+ch[i].second);
}
for(ll i=0;i<ch.size();++i)
{
dp1[u].insert({max(ch[i].first.first,ch[i].first.second+ch[i].second)-ch[i].first.first-ch[i].second,ch1[i]});
mp1[u][ch1[i]]=max(ch[i].first.first,ch[i].first.second+ch[i].second)-ch[i].first.first-ch[i].second;
}
}
ll ans=0;
void dfs1(ll u,ll par)
{
root=u;
/*cout<<"root="<<u<<endl;
for(int i=1;i<=n;i++)
{
cout<<i<<" "<<dp0v[i]<<" "<<getdp1v(i)<<endl;
}*/
ans=max(ans,dp0v[u]);
for(auto v:g[u])
{
if(v.first==par)continue;
root=v.first;
remove(v.first,u);
add(u,v.first,v.second);
dfs1(v.first,u);
rollback1();
rollback2();
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(ll 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);
dfs1(1,0);
cout<<ans<<endl;
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:73:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(ll i=0;i<ch.size();++i)
| ~^~~~~~~~~~
beads.cpp:79:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(ll i=0;i<ch.size();++i)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33260 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
33260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33260 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
33260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33260 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
33260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33260 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
33260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
