kmjp's blog

競技プログラミング参加記です

Codeforces #392 Div2 E. Broken Tree

FよりEの方が難しくない?
http://codeforces.com/contest/758/problem/E

問題

根付き木が与えられる。
各辺eはパラメータとして重さW[e]と強さP[e]が与えられる。

各辺eの強さP[e]は、SubTree内の辺の重さの総和以上でなければならない。
その条件を満たすため、各辺のパラメータを操作することができる。
可能なパラメータ操作はW[e]とP[e]を同じ値(正整数)だけ減らすことで、減らした後W[e]は正、P[e]は非負でなければならない。

パラメータ操作を行うことで、すべての辺に対し強さと重さの条件を満たすことができるか。
できるならパラメータ操作後の辺の状態を示せ。

解法

根付き木の葉から順に処理する。
頂点vにおける親向きの辺eの強さP[e]に対し、vのSubTree内の重さの総和が上回る場合、SubTree内の辺の重さを軽くしていこう。
その際、軽くできる辺の候補はdequeで管理し、葉に近いほど先頭に来るようにする。
P[e]がSubTreeの辺の重さの総和を下回る限り、dequeの先頭から辺を取り出し重さを軽くしていく。
もしdequeが空になってもP[e]がSubTreeの辺の重さの総和を下回らないなら、解はない。

dequeの中身はいわゆるマージテクを使い親に伝搬させていく。
残る問題は、各辺eのW[e]、P[e]をどこまで減らせるかである。
葉から順に各頂点の処理を終えた際、P[e] - (vのSubtree内の辺の重さの総和)分は当然追加で減らすことができる。
そこに加え、SubTree内の辺でまだ重さを減らせる余地があるなら、先にそちらを減らせばその分辺eの重さを減らすことができる。
よって「あとどれだけSubTree内の辺の重さを減らせるか」という値を葉から順に計算しておくことで、以後どれだけ辺eの重さを減らせるかわかる。

int N;
int A[202020],B[202020],W[202020],P[202020];
ll M[202020];
vector<pair<int,int>> E[202020];
ll TW[202020];
ll TR[202020];

deque<int> R[202020];


void dfs(int cur,int pre) {
	
	FORR(e,E[cur]) if(e.second!=pre) {
		dfs(e.second,cur);
		TW[cur]+=TW[e.second];
		if(R[cur].size()<R[e.second].size()) swap(R[cur],R[e.second]);
		FORR(r,R[e.second]) R[cur].push_back(r);
		TR[cur]+=TR[e.second];
	}
	
	FORR(e,E[cur]) if(e.second==pre) {
		int x = e.first;
		
		while(P[e.first]<TW[cur]) {
			if(R[cur].empty()) {
				cout<<-1<<endl;
				exit(0);
			}
			int id=R[cur].front();
			ll red = min(M[id],TW[cur]-P[e.first]);
			TW[cur]-=red;
			W[id]-=red;
			P[id]-=red;
			M[id]-=red;
			TR[cur]-=red;
			if(M[id]==0) R[cur].pop_front();
		}
		
		M[e.first]=min(M[e.first],P[e.first]-(TW[cur]-TR[cur]));
		R[cur].push_back(e.first);
		TW[cur]+=W[e.first];
		TR[cur]+=M[e.first];
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>A[i]>>B[i]>>W[i]>>P[i];
		A[i]--;
		B[i]--;
		E[A[i]].push_back({i,B[i]});
		E[B[i]].push_back({i,A[i]});
		M[i]=min(W[i]-1,P[i]);
	}
	
	dfs(0,-1);
	_P("%d\n",N);
	FOR(i,N-1) _P("%d %d %d %d\n",A[i]+1,B[i]+1,W[i],P[i]);
	
}

まとめ

皆こちらで手こずったせいでFに手が回るのが遅れた?