#include<iostream>
#include<cassert>
#include<vector>
#include<array>
#include<algorithm>
#include<climits>
struct edge{
int n,w;
};
static std::vector<std::vector<edge>> ad;
static std::vector<int> parw;
static std::vector<int> f0,f1,g0,g1;
// f_rf[i]: max value of subtree rooted at i,
// g_rf[i] = ~ but also include edge from i to parent
// where rf = must the component be done first? (0/1)
static auto const b1=[](edge e){
int j=e.n;
return f1[j]+e.w-g0[j];
};
static auto const b2=[](edge e){
int j=e.n;
return f0[j]+e.w-g0[j];
};
static auto const compb1=[](edge a,edge b){
return b1(a)<b1(b);
};
static auto const compb2=[](edge a,edge b){
return b2(a)<b2(b);
};
static void dfs(int i){
int sg0=0; // sum of g0[j] for j in child[i]
int m=INT_MIN; // max cost when use f0 instead of g0 and pair the edge
int m1=INT_MIN; // max cost when use f**1** instead of g0 and pair the edge
int mgf=INT_MIN;
for(edge e:ad[i]){
int j=e.n,w=e.w;
// par[j]=i;
parw[j]=e.w;
ad[j].erase(
std::find_if(begin(ad[j]),end(ad[j]),[i](edge e){
return e.n==i;
}));
dfs(j);
sg0+=g0[j];
m=std::max(m,f0[j]-g0[j]+w);
m1=std::max(m1,f1[j]-g0[j]+w);
mgf=std::max(mgf,g1[j]-g0[j]);
}
f0[i]=sg0; // i cannot be the center of any pair
g0[i]=sg0;
if(m+parw[i]>0)g0[i]+=m+parw[i];
f1[i]=sg0; // if i is constructed first
if(ad[i].size()>=2){ // otherwise, if i is a pair center, one get benefit f1+w-g0 (B1) and another get f0+w-g0 (B2)
// case 1: best B1 get B1, best B2 (except <) get B2
auto const& ai=ad[i];
auto bb1=std::max_element(begin(ai),end(ai),compb1);
int mb2=INT_MIN;
if(bb1!=begin(ai))
mb2=std::max(mb2,
b2(*std::max_element(begin(ai),bb1,compb2)));
if(bb1+1!=end(ai))
mb2=std::max(mb2,
b2(*std::max_element(bb1+1,end(ai),compb2)));
f1[i]=std::max(f1[i],sg0+b1(*bb1)+mb2);
// case 2: best B1 get B2, best B1 of rest get B1
int mb1r=INT_MIN;
if(bb1!=begin(ai))
mb1r=std::max(mb1r,
b1(*std::max_element(begin(ai),bb1,compb1)));
if(bb1+1!=end(ai))
mb1r=std::max(mb1r,
b1(*std::max_element(bb1+1,end(ai),compb1)));
f1[i]=std::max(f1[i],sg0+b2(*bb1)+mb1r);
}
// otherwise (i is not constructed first and not paired) just add max g1-g0
f1[i]=std::max(f1[i],sg0+mgf);
g1[i]=f1[i];
// in case i is a pair center with one leg upward,
// the first vertex constructed must be inside the other leg
g1[i]=std::max(g1[i],sg0+m1+parw[i]);
assert(f1[i]>=f0[i]);
assert(g1[i]>=g0[i]);
assert(g0[i]>=f0[i]);
assert(g1[i]>=f1[i]);
}
int main(){
int n;std::cin>>n;
ad.resize(n);
for(int _=n-1;_--;){
int a,b,w;std::cin>>a>>b>>w;--a;--b;
ad[a].push_back({b,w});
ad[b].push_back({a,w});
}
// par.resize(n);
parw.resize(n);
f0.resize(n);
f1.resize(n);
g0.resize(n);
g1.resize(n);
dfs(0);
std::cout<<f1[0]<<'\n';
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20
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
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
256 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
256 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
6 ms |
768 KB |
Output is correct |
24 |
Correct |
7 ms |
768 KB |
Output is correct |
25 |
Correct |
6 ms |
768 KB |
Output is correct |
26 |
Correct |
12 ms |
1152 KB |
Output is correct |
27 |
Correct |
13 ms |
1152 KB |
Output is correct |
28 |
Correct |
11 ms |
1152 KB |
Output is correct |
29 |
Correct |
11 ms |
1152 KB |
Output is correct |
30 |
Correct |
12 ms |
1152 KB |
Output is correct |
31 |
Correct |
14 ms |
1664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
256 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
6 ms |
768 KB |
Output is correct |
24 |
Correct |
7 ms |
768 KB |
Output is correct |
25 |
Correct |
6 ms |
768 KB |
Output is correct |
26 |
Correct |
12 ms |
1152 KB |
Output is correct |
27 |
Correct |
13 ms |
1152 KB |
Output is correct |
28 |
Correct |
11 ms |
1152 KB |
Output is correct |
29 |
Correct |
11 ms |
1152 KB |
Output is correct |
30 |
Correct |
12 ms |
1152 KB |
Output is correct |
31 |
Correct |
14 ms |
1664 KB |
Output is correct |
32 |
Correct |
66 ms |
4344 KB |
Output is correct |
33 |
Correct |
71 ms |
4344 KB |
Output is correct |
34 |
Correct |
70 ms |
4344 KB |
Output is correct |
35 |
Correct |
335 ms |
16472 KB |
Output is correct |
36 |
Correct |
341 ms |
16504 KB |
Output is correct |
37 |
Correct |
354 ms |
16376 KB |
Output is correct |
38 |
Correct |
272 ms |
16748 KB |
Output is correct |
39 |
Correct |
293 ms |
16868 KB |
Output is correct |
40 |
Correct |
282 ms |
16736 KB |
Output is correct |
41 |
Correct |
331 ms |
22508 KB |
Output is correct |