#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=mp0[where][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;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
/*
u->v
dp[u][0].erase(v)
dp[v][0].insert(u)
dp[u][1].erase(v)
dp[v][1].insert(u)
*/
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)
| ~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
42604 KB |
Output is correct |
2 |
Correct |
25 ms |
42604 KB |
Output is correct |
3 |
Correct |
25 ms |
42604 KB |
Output is correct |
4 |
Correct |
25 ms |
42604 KB |
Output is correct |
5 |
Correct |
24 ms |
42604 KB |
Output is correct |
6 |
Correct |
26 ms |
42604 KB |
Output is correct |
7 |
Correct |
25 ms |
42604 KB |
Output is correct |
8 |
Correct |
25 ms |
42604 KB |
Output is correct |
9 |
Correct |
25 ms |
42604 KB |
Output is correct |
10 |
Correct |
25 ms |
42604 KB |
Output is correct |
11 |
Correct |
25 ms |
42604 KB |
Output is correct |
12 |
Correct |
25 ms |
42604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
42604 KB |
Output is correct |
2 |
Correct |
25 ms |
42604 KB |
Output is correct |
3 |
Correct |
25 ms |
42604 KB |
Output is correct |
4 |
Correct |
25 ms |
42604 KB |
Output is correct |
5 |
Correct |
24 ms |
42604 KB |
Output is correct |
6 |
Correct |
26 ms |
42604 KB |
Output is correct |
7 |
Correct |
25 ms |
42604 KB |
Output is correct |
8 |
Correct |
25 ms |
42604 KB |
Output is correct |
9 |
Correct |
25 ms |
42604 KB |
Output is correct |
10 |
Correct |
25 ms |
42604 KB |
Output is correct |
11 |
Correct |
25 ms |
42604 KB |
Output is correct |
12 |
Correct |
25 ms |
42604 KB |
Output is correct |
13 |
Correct |
25 ms |
42604 KB |
Output is correct |
14 |
Correct |
25 ms |
42604 KB |
Output is correct |
15 |
Correct |
25 ms |
42604 KB |
Output is correct |
16 |
Correct |
27 ms |
42732 KB |
Output is correct |
17 |
Correct |
25 ms |
42732 KB |
Output is correct |
18 |
Correct |
26 ms |
42732 KB |
Output is correct |
19 |
Correct |
25 ms |
42732 KB |
Output is correct |
20 |
Correct |
27 ms |
42732 KB |
Output is correct |
21 |
Correct |
25 ms |
42732 KB |
Output is correct |
22 |
Correct |
26 ms |
42732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
42604 KB |
Output is correct |
2 |
Correct |
25 ms |
42604 KB |
Output is correct |
3 |
Correct |
25 ms |
42604 KB |
Output is correct |
4 |
Correct |
25 ms |
42604 KB |
Output is correct |
5 |
Correct |
24 ms |
42604 KB |
Output is correct |
6 |
Correct |
26 ms |
42604 KB |
Output is correct |
7 |
Correct |
25 ms |
42604 KB |
Output is correct |
8 |
Correct |
25 ms |
42604 KB |
Output is correct |
9 |
Correct |
25 ms |
42604 KB |
Output is correct |
10 |
Correct |
25 ms |
42604 KB |
Output is correct |
11 |
Correct |
25 ms |
42604 KB |
Output is correct |
12 |
Correct |
25 ms |
42604 KB |
Output is correct |
13 |
Correct |
25 ms |
42604 KB |
Output is correct |
14 |
Correct |
25 ms |
42604 KB |
Output is correct |
15 |
Correct |
25 ms |
42604 KB |
Output is correct |
16 |
Correct |
27 ms |
42732 KB |
Output is correct |
17 |
Correct |
25 ms |
42732 KB |
Output is correct |
18 |
Correct |
26 ms |
42732 KB |
Output is correct |
19 |
Correct |
25 ms |
42732 KB |
Output is correct |
20 |
Correct |
27 ms |
42732 KB |
Output is correct |
21 |
Correct |
25 ms |
42732 KB |
Output is correct |
22 |
Correct |
26 ms |
42732 KB |
Output is correct |
23 |
Correct |
34 ms |
44268 KB |
Output is correct |
24 |
Correct |
39 ms |
44268 KB |
Output is correct |
25 |
Correct |
35 ms |
44268 KB |
Output is correct |
26 |
Correct |
52 ms |
45804 KB |
Output is correct |
27 |
Correct |
44 ms |
45804 KB |
Output is correct |
28 |
Correct |
60 ms |
45988 KB |
Output is correct |
29 |
Correct |
57 ms |
45932 KB |
Output is correct |
30 |
Correct |
58 ms |
45932 KB |
Output is correct |
31 |
Correct |
52 ms |
47020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
42604 KB |
Output is correct |
2 |
Correct |
25 ms |
42604 KB |
Output is correct |
3 |
Correct |
25 ms |
42604 KB |
Output is correct |
4 |
Correct |
25 ms |
42604 KB |
Output is correct |
5 |
Correct |
24 ms |
42604 KB |
Output is correct |
6 |
Correct |
26 ms |
42604 KB |
Output is correct |
7 |
Correct |
25 ms |
42604 KB |
Output is correct |
8 |
Correct |
25 ms |
42604 KB |
Output is correct |
9 |
Correct |
25 ms |
42604 KB |
Output is correct |
10 |
Correct |
25 ms |
42604 KB |
Output is correct |
11 |
Correct |
25 ms |
42604 KB |
Output is correct |
12 |
Correct |
25 ms |
42604 KB |
Output is correct |
13 |
Correct |
25 ms |
42604 KB |
Output is correct |
14 |
Correct |
25 ms |
42604 KB |
Output is correct |
15 |
Correct |
25 ms |
42604 KB |
Output is correct |
16 |
Correct |
27 ms |
42732 KB |
Output is correct |
17 |
Correct |
25 ms |
42732 KB |
Output is correct |
18 |
Correct |
26 ms |
42732 KB |
Output is correct |
19 |
Correct |
25 ms |
42732 KB |
Output is correct |
20 |
Correct |
27 ms |
42732 KB |
Output is correct |
21 |
Correct |
25 ms |
42732 KB |
Output is correct |
22 |
Correct |
26 ms |
42732 KB |
Output is correct |
23 |
Correct |
34 ms |
44268 KB |
Output is correct |
24 |
Correct |
39 ms |
44268 KB |
Output is correct |
25 |
Correct |
35 ms |
44268 KB |
Output is correct |
26 |
Correct |
52 ms |
45804 KB |
Output is correct |
27 |
Correct |
44 ms |
45804 KB |
Output is correct |
28 |
Correct |
60 ms |
45988 KB |
Output is correct |
29 |
Correct |
57 ms |
45932 KB |
Output is correct |
30 |
Correct |
58 ms |
45932 KB |
Output is correct |
31 |
Correct |
52 ms |
47020 KB |
Output is correct |
32 |
Correct |
158 ms |
58604 KB |
Output is correct |
33 |
Correct |
159 ms |
58476 KB |
Output is correct |
34 |
Correct |
158 ms |
58476 KB |
Output is correct |
35 |
Correct |
647 ms |
106092 KB |
Output is correct |
36 |
Correct |
649 ms |
106220 KB |
Output is correct |
37 |
Correct |
640 ms |
106112 KB |
Output is correct |
38 |
Execution timed out |
1100 ms |
111180 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |