TopCoder SRM 763 : Div1 Medium RootItRight

こういうのTopCoderで出るのか…。
https://community.topcoder.com/stat?c=problem_statement&pm=15564&rd=17614

問題

木を成す無向グラフが与えられる。
各点vには値V[v]が設定されている。

根頂点をrとするとき、頂点xに対する関数C(r,x)を以下のように定義する。

• rからxへのパスをs0,s1,s1,...skとするとき、C(r,x) = sum(i*si)

D(r)を、全頂点xに対するC(r,x)の和とする。D(r)の最小値を求めよ。

解法

D(r)を実際に全頂点について求める。D(r)を当然愚直に行うとTLEするので、全方位木DPを利用しよう。
rが固定されているとき、D(r)を計算する過程でV[x]がどの程度寄与するかを考えると、V[x]*dist(r,x)*(xのSubTreeの頂点数)となる。
そこで、部分木に対し以下の３値を持っておこう。

• 頂点数
• V[v]の和
• (根頂点からの距離)*V[v]の和

あとは根頂点を1ずつずらしたときにそれぞれがどの程度ずれるか見ていけばよい。

int N;
vector<int> E[404040];
int C[202020];
ll T[202020];
ll S[202020];
ll V[202020];

class RootItRight {
	public:
	
	void dfs(int cur,int pre) {
		C[cur]=1;
		FORR(e,E[cur]) if(e!=pre) {
			dfs(e,cur);
			C[cur]+=C[e];
			T[cur]+=T[e];
			S[cur]+=S[e];
		}
		S[cur]+=T[cur];
		T[cur]+=C[cur]*V[cur];
		//cout<<cur<<" "<<T[cur]<<" "<<S[cur]<<endl;
	}
	
	void dfs2(int cur,int pre,ll PT,ll PS) {
		PS+=PT;
		S[cur]+=PS;
		//cout<<cur<<" "<<T[cur]<<" "<<S[cur]<<" "<<PT<<" "<<PS<<endl;
		T[cur]-=C[cur]*V[cur];
		
		
		FORR(e,E[cur]) if(e!=pre) {
			
			T[cur]+=(N-C[e])*V[cur];
			dfs2(e,cur,PT+T[cur]-T[e],S[cur]-S[e]-T[e]);
			T[cur]-=(N-C[e])*V[cur];
			
		}
		
	}
	
	long long findMinimumTotalCost(int N_, vector <int> edge, vector <int> V_, int D, int seed, int MX) {
		N=N_;
		vector<ll> A(2*N);
		A[0]=seed;
		int i;
		for(i=1;i<=2*N-1;i++) A[i] = (A[i-1] * 1103515245LL + 12345) % 2147483648;
		for(i=edge.size();i<N;i++) {
			edge.push_back((A[i]%min(i,D))+i-min(i,D));
		}
		
		FOR(i,N) E[i].clear();
		for(i=1;i<=N-1;i++) {
			E[i].push_back(edge[i]);
			E[edge[i]].push_back(i);
		}
		for(i=V_.size();i<=N-1;i++) V_.push_back(A[N+i]%MX);
		FOR(i,N) V[i]=V_[i];
		
		ZERO(C);
		ZERO(T);
		ZERO(S);
		
		dfs(0,-1);
		dfs2(0,-1,0,0);
		
		return *min_element(S,S+N);
	}
}

まとめ

方針はすぐ見えるけど実装が面倒な問題だった。