#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
const ll INF=2e15;
int n;
vector<pair<int,ll> >g[MAXN];
set<pair<ll,int> >dp1[MAXN];
unordered_map<int,ll>mp1[MAXN];
unordered_map<int,ll>mp0[MAXN];
ll dp0v[MAXN];
int root;
ll getdp1v(int u)
{
if(dp1[u].size()==0)return -INF;
return dp0v[u]-(*dp1[u].begin()).first;
}
struct save1
{
int what,where;
ll w0,w1;
};
struct save2
{
ll mx;
int what,where;
ll weight,dp0vwhat;
};
stack<save1>st1;
stack<save2>st2;
void remove(int what,int where)
{
ll w0=mp0[where][what];
dp0v[where]-=w0;
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;
dp1[xd.where].insert({xd.w1,xd.what});
}
void add(int what,int where,ll weight)
{
ll mx=max(dp0v[what],getdp1v(what)+weight);
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();
dp0v[xd.where]-=xd.mx;
dp1[xd.where].erase({xd.mx-xd.dp0vwhat-xd.weight,xd.what});
}
void dfs(int u,int p)
{
vector<pair<pair<ll,ll>,ll> >ch;
vector<int>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(int i=0;i<ch.size();++i)
{
dp0v[u]+=max(ch[i].first.first,ch[i].first.second+ch[i].second);
mp0[u][ch1[i]]=max(ch[i].first.first,ch[i].first.second+ch[i].second);
}
for(int 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(int u,int par)
{
root=u;
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);
srand(420);
cin>>n;
for(int i=1;i<n;++i)
{
int x,y;
ll 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<<"\n";
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:70:15: warning: comparison of integer expressions of different signedness: '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]
70 | for(int i=0;i<ch.size();++i)
| ~^~~~~~~~~~
beads.cpp:75:15: warning: comparison of integer expressions of different signedness: '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]
75 | for(int i=0;i<ch.size();++i)
| ~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
36332 KB |
Output is correct |
2 |
Correct |
25 ms |
36332 KB |
Output is correct |
3 |
Correct |
25 ms |
36332 KB |
Output is correct |
4 |
Correct |
25 ms |
36332 KB |
Output is correct |
5 |
Correct |
27 ms |
36332 KB |
Output is correct |
6 |
Correct |
25 ms |
36332 KB |
Output is correct |
7 |
Correct |
27 ms |
36332 KB |
Output is correct |
8 |
Correct |
27 ms |
36332 KB |
Output is correct |
9 |
Correct |
25 ms |
36332 KB |
Output is correct |
10 |
Correct |
25 ms |
36332 KB |
Output is correct |
11 |
Correct |
25 ms |
36332 KB |
Output is correct |
12 |
Correct |
25 ms |
36332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
36332 KB |
Output is correct |
2 |
Correct |
25 ms |
36332 KB |
Output is correct |
3 |
Correct |
25 ms |
36332 KB |
Output is correct |
4 |
Correct |
25 ms |
36332 KB |
Output is correct |
5 |
Correct |
27 ms |
36332 KB |
Output is correct |
6 |
Correct |
25 ms |
36332 KB |
Output is correct |
7 |
Correct |
27 ms |
36332 KB |
Output is correct |
8 |
Correct |
27 ms |
36332 KB |
Output is correct |
9 |
Correct |
25 ms |
36332 KB |
Output is correct |
10 |
Correct |
25 ms |
36332 KB |
Output is correct |
11 |
Correct |
25 ms |
36332 KB |
Output is correct |
12 |
Correct |
25 ms |
36332 KB |
Output is correct |
13 |
Correct |
26 ms |
36332 KB |
Output is correct |
14 |
Correct |
25 ms |
36332 KB |
Output is correct |
15 |
Correct |
25 ms |
36332 KB |
Output is correct |
16 |
Correct |
27 ms |
36460 KB |
Output is correct |
17 |
Correct |
26 ms |
36460 KB |
Output is correct |
18 |
Correct |
26 ms |
36460 KB |
Output is correct |
19 |
Correct |
25 ms |
36460 KB |
Output is correct |
20 |
Correct |
26 ms |
36460 KB |
Output is correct |
21 |
Correct |
26 ms |
36480 KB |
Output is correct |
22 |
Correct |
25 ms |
36460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
36332 KB |
Output is correct |
2 |
Correct |
25 ms |
36332 KB |
Output is correct |
3 |
Correct |
25 ms |
36332 KB |
Output is correct |
4 |
Correct |
25 ms |
36332 KB |
Output is correct |
5 |
Correct |
27 ms |
36332 KB |
Output is correct |
6 |
Correct |
25 ms |
36332 KB |
Output is correct |
7 |
Correct |
27 ms |
36332 KB |
Output is correct |
8 |
Correct |
27 ms |
36332 KB |
Output is correct |
9 |
Correct |
25 ms |
36332 KB |
Output is correct |
10 |
Correct |
25 ms |
36332 KB |
Output is correct |
11 |
Correct |
25 ms |
36332 KB |
Output is correct |
12 |
Correct |
25 ms |
36332 KB |
Output is correct |
13 |
Correct |
26 ms |
36332 KB |
Output is correct |
14 |
Correct |
25 ms |
36332 KB |
Output is correct |
15 |
Correct |
25 ms |
36332 KB |
Output is correct |
16 |
Correct |
27 ms |
36460 KB |
Output is correct |
17 |
Correct |
26 ms |
36460 KB |
Output is correct |
18 |
Correct |
26 ms |
36460 KB |
Output is correct |
19 |
Correct |
25 ms |
36460 KB |
Output is correct |
20 |
Correct |
26 ms |
36460 KB |
Output is correct |
21 |
Correct |
26 ms |
36480 KB |
Output is correct |
22 |
Correct |
25 ms |
36460 KB |
Output is correct |
23 |
Correct |
33 ms |
37484 KB |
Output is correct |
24 |
Correct |
33 ms |
37484 KB |
Output is correct |
25 |
Correct |
32 ms |
37484 KB |
Output is correct |
26 |
Correct |
42 ms |
38636 KB |
Output is correct |
27 |
Correct |
45 ms |
38636 KB |
Output is correct |
28 |
Correct |
43 ms |
38704 KB |
Output is correct |
29 |
Correct |
42 ms |
38636 KB |
Output is correct |
30 |
Correct |
41 ms |
38508 KB |
Output is correct |
31 |
Correct |
44 ms |
39532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
36332 KB |
Output is correct |
2 |
Correct |
25 ms |
36332 KB |
Output is correct |
3 |
Correct |
25 ms |
36332 KB |
Output is correct |
4 |
Correct |
25 ms |
36332 KB |
Output is correct |
5 |
Correct |
27 ms |
36332 KB |
Output is correct |
6 |
Correct |
25 ms |
36332 KB |
Output is correct |
7 |
Correct |
27 ms |
36332 KB |
Output is correct |
8 |
Correct |
27 ms |
36332 KB |
Output is correct |
9 |
Correct |
25 ms |
36332 KB |
Output is correct |
10 |
Correct |
25 ms |
36332 KB |
Output is correct |
11 |
Correct |
25 ms |
36332 KB |
Output is correct |
12 |
Correct |
25 ms |
36332 KB |
Output is correct |
13 |
Correct |
26 ms |
36332 KB |
Output is correct |
14 |
Correct |
25 ms |
36332 KB |
Output is correct |
15 |
Correct |
25 ms |
36332 KB |
Output is correct |
16 |
Correct |
27 ms |
36460 KB |
Output is correct |
17 |
Correct |
26 ms |
36460 KB |
Output is correct |
18 |
Correct |
26 ms |
36460 KB |
Output is correct |
19 |
Correct |
25 ms |
36460 KB |
Output is correct |
20 |
Correct |
26 ms |
36460 KB |
Output is correct |
21 |
Correct |
26 ms |
36480 KB |
Output is correct |
22 |
Correct |
25 ms |
36460 KB |
Output is correct |
23 |
Correct |
33 ms |
37484 KB |
Output is correct |
24 |
Correct |
33 ms |
37484 KB |
Output is correct |
25 |
Correct |
32 ms |
37484 KB |
Output is correct |
26 |
Correct |
42 ms |
38636 KB |
Output is correct |
27 |
Correct |
45 ms |
38636 KB |
Output is correct |
28 |
Correct |
43 ms |
38704 KB |
Output is correct |
29 |
Correct |
42 ms |
38636 KB |
Output is correct |
30 |
Correct |
41 ms |
38508 KB |
Output is correct |
31 |
Correct |
44 ms |
39532 KB |
Output is correct |
32 |
Correct |
133 ms |
47596 KB |
Output is correct |
33 |
Correct |
131 ms |
47468 KB |
Output is correct |
34 |
Correct |
141 ms |
47468 KB |
Output is correct |
35 |
Correct |
549 ms |
80620 KB |
Output is correct |
36 |
Correct |
547 ms |
80748 KB |
Output is correct |
37 |
Correct |
565 ms |
80620 KB |
Output is correct |
38 |
Correct |
802 ms |
82640 KB |
Output is correct |
39 |
Correct |
703 ms |
83432 KB |
Output is correct |
40 |
Correct |
633 ms |
81880 KB |
Output is correct |
41 |
Correct |
716 ms |
95688 KB |
Output is correct |