TopCoder SRM 744 Div1 Hard CoverTreePaths

これはもうちょっと考えていくべきだった…。
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;
	}
}

まとめ

双対とか理解してないけど、結果的にやったことはこんな感じなんだろうな。