これも本番どうにか解いてるな。
https://codeforces.com/contest/1637/problem/F
問題
N頂点の木を成すグラフが与えられる。
各点vには高さH[v]が設定されている。
各点vに非負整数E[v]を割り当てたい。
その際、各点xに対し、パス上にxを含む端点(u,v)のうち、min(E[u],E[v])≧H[x]となるようにしたい。
Eの総和の最小値を求めよ。
解法
根以外の頂点vのSubTreeに対し、その中のEの総和と最大値を取るようにしよう。
vの配下にH[v]以上のものがない場合、SubTree以下で最大のE(u)に対しH[v]-E(u)だけ加算して、SubTree内にH[v]以上の点が少なくとも1個できるようにする。
根頂点rについては、同様にH[r]以上の点が2個以上できるようにすればよい。
int N; ll H[202020]; vector<int> E[202020]; pair<ll,ll> dfs(int cur,int pre) { ll sum=0; if(cur!=pre) { ll ma=0; FORR(e,E[cur]) if(e!=pre) { auto p=dfs(e,cur); sum+=p.first; ma=max(ma,p.second); } if(H[cur]>ma) { sum+=H[cur]-ma; ma=H[cur]; } return {sum,ma}; } else { vector<ll> C={0,0}; FORR(e,E[cur]) if(e!=pre) { auto p=dfs(e,cur); sum+=p.first; C.push_back(p.second); } sort(ALL(C)); reverse(ALL(C)); sum+=H[cur]-C[0]; sum+=H[cur]-C[1]; return {sum,H[cur]}; } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; ll ma=0; j=0; FOR(i,N) { cin>>H[i]; ma=max(ma,H[i]); if(H[i]==ma) j=i; } FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } auto p=dfs(j,j); cout<<p.first<<endl; }
まとめ
まぁ割とシンプルな問題。