#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(m,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
if(mgf>0)
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
if(m1>INT_MIN)
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 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
