これはもうちょっと考えていくべきだった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14587
問題
根付き木が与えられる。
各頂点iにはパラメータD[i]、C[i]が設定されている。
またiの親頂点をP[i]とする。
各頂点に非負整数V[i]を割り当てたい。
この時、各頂点iに対して、その頂点から根に至るパス上の頂点jにおけるV[j]の総和がD[i]以上としなければならない。
なお、頂点iの値V[i]に対し、コストV[i]*C[i]が生じるものとする。
D[i]に関する条件を満たす範囲でV[i]を設定する際、コストの総和の最小値を求めよ。
解法
まずD[i]の値を整理しよう。
自身の祖先jにD[j]>D[i]となる点がある場合、パスroot-jの間でV[*]の総和がD[i]以上になるので、D[i]=D[j]とみなしてもよい。
よって最初にD[i]=max(D[iの祖先])と書き換えよう。
その後、E[i] = D[i]-D[P[i]]を考える。
これはroot-P[i]の間ですでにD[i]分値が設定されていたとして、root-iの間でもう(D[i]-D[P[i]])分だけ値を追加しなければならないことを意味する。
以後D[i]は考えなくてよくE[i]を考えていこう。
葉から順に、各頂点vに対しmap(v)[c]=nを更新していく。
これはvのsubtree内で、コストcの頂点で設定された値がn個ある、ということを意味する。
最終的にmap(root)においてc*nの総和が解となる。
子頂点v'に対しmap(v')がわかった状態でmap(v)を構築しよう。
まず最初にmap(v)[C[i]]=E[i]を設定しておく。これはvの祖先で設定しなければいけない値は、vのSubTree内ではとりあえずvで設定しておくしかないためである。
各子頂点のmapから最大値の総和sを取り、map(v)[min(s,C[i])]++を繰り返せばよい。
これは各子頂点内でそれぞれ値を1追加する場合と、vに1追加する場合の小さい方を選ぶことを意味する。
実際は愚直に1ずつ行うとTLEするので、同じ値をまとめて処理したり、子頂点が1個の場合はマージテクを用いて高速化したりする必要がある。
map<ll,ll> M[101010]; vector<int> C[101010]; class CoverTreePaths { public: long long minimumCost(int n, vector <int> p, vector <int> d, vector <int> c, vector <int> params) { int i; p.insert(p.begin(),0); for(int i=p.size();i<n;i++) { p.push_back((params[0]*1LL*p.back()+params[1])%i); d.push_back(1+(params[2]*1LL*d.back()+params[3])%params[4]); c.push_back(1+(params[5]*1LL*c.back()+params[6])%params[7]); } FOR(i,n) { M[i].clear(); C[i].clear(); if(i) { d[i]=max(d[i],d[p[i]]); C[p[i]].push_back(i); } } for(i=n-1;i>=0;i--) { if(i) d[i]-=d[p[i]]; M[i][c[i]]=d[i]; while(1) { int ok=0; ll sum=0; ll num=1LL<<50; FORR(v,C[i]) { if(M[v].size()) { ok++; sum+=M[v].rbegin()->first; num=min(num,M[v].rbegin()->second); } } if(ok<=1) break; M[i][min((ll)c[i],sum)]+=num; FORR(v,C[i]) if(M[v].size()) { M[v].rbegin()->second-=num; if(M[v].rbegin()->second==0) M[v].erase(M[v].rbegin()->first); } } FORR(v,C[i]) if(M[v].size()) { while(M[v].size() && M[v].rbegin()->first>c[i]) { M[i][c[i]]+=M[v].rbegin()->second; M[v].erase(M[v].rbegin()->first); } if(M[v].size()>M[i].size()) swap(M[i],M[v]); FORR(m,M[v]) M[i][m.first]+=m.second; M[v].clear(); } } ll ret=0; FORR(m,M[0]) ret+=m.first*m.second; return ret; } }
まとめ
双対とか理解してないけど、結果的にやったことはこんな感じなんだろうな。