年明けyukicoderが多くて記事未作成の問題が溜まってるのだけど、Codeforcesもたまってるのでこちらから。
https://codeforces.com/contest/1363/problem/E
問題
根付き木が与えられる。
各頂点には、コストA[i]、現在のバイナリ値B[i]、目標のバイナリ値C[i]が与えられる。
以下の処理を任意回数行う。
- 頂点vを指定し、vのSubTree内の頂点を任意個選び、バイナリ値を任意にシャッフルする。その際、k個の頂点をシャッフルするコストはA[v]*k
全頂点のバイナリ値を、目標の通りにする最小コストを求めよ。
解法
親の方がコストが低いなら、ある頂点でシャッフルするより親頂点でシャッフルした方がよい。
言い換えれば、親頂点と同じコストでシャッフル可能である。
そのため、事前にA[v]=min(A[v],A[parent[v]])でA[v]を更新しておこう。
こうすると、A[v]は根から葉に向けて降順、すなわちシャッフルは可能な限り葉に近いところで行うのが良いことになる。
あと頂点をDFSしつつ、余った0,1をできるだけ根に近い位置でどん欲にシャフルしていこう。
int N; ll A[201010]; int T[202020][2]; int B[201010],C[201010]; vector<int> E[201010]; ll ret; void dfs(int cur,int pre) { if(pre!=cur) A[cur]=min(A[cur],A[pre]); int F[2]={}; if(B[cur]>C[cur]) F[0]++; if(B[cur]<C[cur]) F[1]++; FORR(e,E[cur]) if(e!=pre) { dfs(e,cur); F[0]+=T[e][0]; F[1]+=T[e][1]; } ret+=2*min(F[0],F[1])*A[cur]; T[cur][0]=F[0]-min(F[0],F[1]); T[cur][1]=F[1]-min(F[0],F[1]); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>A[i]>>B[i]>>C[i]; } FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } dfs(0,0); if(T[0][0]||T[0][1]) { cout<<"-1"<<endl; } else { cout<<ret<<endl; } }
まとめ
これはDiv2Eにしては簡単。