#include<bits/stdc++.h>
using namespace std;
const long long N=1000000000000000000LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,pas,dp[200009],dp2[200009];
pair <long long, long long> msh[200009];
vector <pair <long long, long long> > v[200009];
multiset <long long> s[200009];
multiset <long long>::iterator tt;
void dfsst(long long q, long long w){
long long qw=-N;
for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it).first==w) continue;
msh[(*it).first]=make_pair(q,(*it).second);
dfsst((*it).first,q);
dp[q]+=max(dp[(*it).first],dp2[(*it).first]);
if(qw<(*it).second+dp[(*it).first]-max(dp[(*it).first],dp2[(*it).first])) qw=(*it).second+dp[(*it).first]-max(dp[(*it).first],dp2[(*it).first]);
s[q].insert((*it).second+dp[(*it).first]-max(dp[(*it).first],dp2[(*it).first]));
}
if(qw!=-N){
dp2[q]=msh[q].second+dp[q]+qw;
}else{
dp2[q]=-N;
}
}
void rt(long long q, long long w){
dp[q]-=max(dp[w],dp2[w]);
long long qw=msh[w].second+dp[w]-max(dp[w],dp2[w]);
s[q].erase(s[q].lower_bound(qw));
msh[q].first=w;msh[q].second=msh[w].second;
if(s[q].size()!=0){
tt=s[q].end();
tt--;
dp2[q]=msh[q].second+dp[q]+(*tt);
}else{
dp2[q]=-N;
}
s[w].insert(msh[q].second+dp[q]-max(dp[q],dp2[q]));
dp[w]+=max(dp[q],dp2[q]);
}
void dfs(long long q, long long w){
pas=max(pas,dp[q]);
for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it).first==w) continue;
rt(q,(*it).first);
dfs((*it).first,q);
rt((*it).first,q);
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;
for(i=1; i<a; i++){
cin>>c>>d>>e;
v[c].push_back(make_pair(d,e));
v[d].push_back(make_pair(c,e));
}
dfsst(1,0);
dfs(1,0);
cout<<pas;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14428 KB |
Output is correct |
3 |
Correct |
8 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14396 KB |
Output is correct |
5 |
Correct |
8 ms |
14412 KB |
Output is correct |
6 |
Correct |
9 ms |
14412 KB |
Output is correct |
7 |
Correct |
8 ms |
14412 KB |
Output is correct |
8 |
Correct |
8 ms |
14412 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
9 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
8 ms |
14424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14428 KB |
Output is correct |
3 |
Correct |
8 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14396 KB |
Output is correct |
5 |
Correct |
8 ms |
14412 KB |
Output is correct |
6 |
Correct |
9 ms |
14412 KB |
Output is correct |
7 |
Correct |
8 ms |
14412 KB |
Output is correct |
8 |
Correct |
8 ms |
14412 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
9 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
8 ms |
14424 KB |
Output is correct |
13 |
Correct |
9 ms |
14412 KB |
Output is correct |
14 |
Correct |
9 ms |
14344 KB |
Output is correct |
15 |
Correct |
9 ms |
14336 KB |
Output is correct |
16 |
Correct |
9 ms |
14412 KB |
Output is correct |
17 |
Correct |
9 ms |
14412 KB |
Output is correct |
18 |
Correct |
9 ms |
14412 KB |
Output is correct |
19 |
Correct |
9 ms |
14412 KB |
Output is correct |
20 |
Correct |
9 ms |
14540 KB |
Output is correct |
21 |
Correct |
9 ms |
14412 KB |
Output is correct |
22 |
Correct |
9 ms |
14452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14428 KB |
Output is correct |
3 |
Correct |
8 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14396 KB |
Output is correct |
5 |
Correct |
8 ms |
14412 KB |
Output is correct |
6 |
Correct |
9 ms |
14412 KB |
Output is correct |
7 |
Correct |
8 ms |
14412 KB |
Output is correct |
8 |
Correct |
8 ms |
14412 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
9 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
8 ms |
14424 KB |
Output is correct |
13 |
Correct |
9 ms |
14412 KB |
Output is correct |
14 |
Correct |
9 ms |
14344 KB |
Output is correct |
15 |
Correct |
9 ms |
14336 KB |
Output is correct |
16 |
Correct |
9 ms |
14412 KB |
Output is correct |
17 |
Correct |
9 ms |
14412 KB |
Output is correct |
18 |
Correct |
9 ms |
14412 KB |
Output is correct |
19 |
Correct |
9 ms |
14412 KB |
Output is correct |
20 |
Correct |
9 ms |
14540 KB |
Output is correct |
21 |
Correct |
9 ms |
14412 KB |
Output is correct |
22 |
Correct |
9 ms |
14452 KB |
Output is correct |
23 |
Correct |
12 ms |
15052 KB |
Output is correct |
24 |
Correct |
13 ms |
15052 KB |
Output is correct |
25 |
Correct |
13 ms |
15052 KB |
Output is correct |
26 |
Correct |
21 ms |
15692 KB |
Output is correct |
27 |
Correct |
17 ms |
15728 KB |
Output is correct |
28 |
Correct |
20 ms |
15656 KB |
Output is correct |
29 |
Correct |
20 ms |
15668 KB |
Output is correct |
30 |
Correct |
19 ms |
15692 KB |
Output is correct |
31 |
Correct |
18 ms |
16052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14428 KB |
Output is correct |
3 |
Correct |
8 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14396 KB |
Output is correct |
5 |
Correct |
8 ms |
14412 KB |
Output is correct |
6 |
Correct |
9 ms |
14412 KB |
Output is correct |
7 |
Correct |
8 ms |
14412 KB |
Output is correct |
8 |
Correct |
8 ms |
14412 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
9 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
8 ms |
14424 KB |
Output is correct |
13 |
Correct |
9 ms |
14412 KB |
Output is correct |
14 |
Correct |
9 ms |
14344 KB |
Output is correct |
15 |
Correct |
9 ms |
14336 KB |
Output is correct |
16 |
Correct |
9 ms |
14412 KB |
Output is correct |
17 |
Correct |
9 ms |
14412 KB |
Output is correct |
18 |
Correct |
9 ms |
14412 KB |
Output is correct |
19 |
Correct |
9 ms |
14412 KB |
Output is correct |
20 |
Correct |
9 ms |
14540 KB |
Output is correct |
21 |
Correct |
9 ms |
14412 KB |
Output is correct |
22 |
Correct |
9 ms |
14452 KB |
Output is correct |
23 |
Correct |
12 ms |
15052 KB |
Output is correct |
24 |
Correct |
13 ms |
15052 KB |
Output is correct |
25 |
Correct |
13 ms |
15052 KB |
Output is correct |
26 |
Correct |
21 ms |
15692 KB |
Output is correct |
27 |
Correct |
17 ms |
15728 KB |
Output is correct |
28 |
Correct |
20 ms |
15656 KB |
Output is correct |
29 |
Correct |
20 ms |
15668 KB |
Output is correct |
30 |
Correct |
19 ms |
15692 KB |
Output is correct |
31 |
Correct |
18 ms |
16052 KB |
Output is correct |
32 |
Correct |
65 ms |
20820 KB |
Output is correct |
33 |
Correct |
70 ms |
20884 KB |
Output is correct |
34 |
Correct |
63 ms |
20812 KB |
Output is correct |
35 |
Correct |
360 ms |
40312 KB |
Output is correct |
36 |
Correct |
360 ms |
40392 KB |
Output is correct |
37 |
Correct |
369 ms |
40336 KB |
Output is correct |
38 |
Correct |
448 ms |
39524 KB |
Output is correct |
39 |
Correct |
422 ms |
39468 KB |
Output is correct |
40 |
Correct |
433 ms |
39452 KB |
Output is correct |
41 |
Correct |
433 ms |
44764 KB |
Output is correct |