Codeforces #1075 : Div2 F. Zhora the Vacuum Cleaner

なんでナッツと掃除機という設定なんだろう。
https://codeforces.com/contest/2189/problem/F

問題

木を成す無向グラフが与えられる。
各点には、非負整数個のナッツがあり、それぞれの個数は入力で与えられる。

以下を行いすべてのナッツを回収するのにかかるコストの最小値を求めよ。

• 点vを指定し、１回処理すると、v以外の各点にあるナッツのうち、１つがv側に近い点に移動する。なお、この移動はvから遠い順に行われる。このコストはPである。
• 指定した点のナッツをすべて回収する。このコストはQである。

解法

全方位木DPの要領で、各辺のうち、片側からもう片側にナッツを寄せ切るのにかかる処理回数がわかる。
ここから、各点のナッツを空にするのにかかる前者の処理の最小回数がわかる。
あとはその回数の配列を昇順にソートし、ナッツが空の頂点数を総当たりしてコストの最小値を求めよう。

int T,N,P,Q;
int A[202020];
ll S[202020];
vector<int> E[202020];
int dead[202020];
map<pair<int,int>,ll> M;
ll SA;
int dfs(int cur,int pre) {
	int sum=A[cur]>0;
	FORR(e,E[cur]) if(e!=pre) sum+=dfs(e,cur);
	if(sum<=1&&A[cur]==0) dead[cur]=1;
	return sum>0;
}

void dfs2(int cur,int pre) {
	S[cur]=A[cur];
	FORR(e,E[cur]) if(e!=pre) {
		dfs2(e,cur);
		S[cur]+=S[e];
	}
	M[{cur,pre}]=S[cur];
	M[{pre,cur}]=SA-S[cur];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>P>>Q;
		SA=0;
		FOR(i,N) {
			cin>>A[i];
			E[i].clear();
			dead[i]=0;
			SA+=A[i];
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		FOR(i,N) if(A[i]) {
			dfs(i,i);
			break;
		}
		if(i==N) {
			//1個もない
			cout<<0<<endl;
			continue;
		}
		M.clear();
		FORR(e,E[0]) dfs2(e,0);
		
		vector<ll> cand;
		FOR(i,N) {
			ll mi=1LL<<60;
			if(dead[i]) mi=0;
			FORR(e,E[i]) mi=min(mi,M[{i,e}]);
			cand.push_back(mi);
		}
		sort(ALL(cand));
		ll ret=0;
		FOR(i,N) if(A[i]) ret+=Q;
		for(x=1;x<N;x++) ret=min(ret,1LL*(N-x)*Q+1LL*cand[x-1]*P);
		cout<<ret<<endl;
		
	}
		
}

まとめ

うーん、辺の片側にナッツを寄せ切ればよいっていう発想が出ないな…。