Codeforces #664 Div1 D. Boboniu and Jianghu

Div1Dの割には簡単目な問題。
https://codeforces.com/contest/1394/problem/D

問題

木を成す無向グラフが与えられる。
各点には高さH[i]とつまらなさT[i]が与えられる。

この木の辺を、いくつかのパスでカバーすることを考える。
その際、

• 各辺はいずれかのパスで1度だけ登場すること
• 各頂点は、複数のパスで登場してもよい
• パスは、高さが低い方から高い方に向けて流れなければならない。（高さが同じ頂点間はどちらのパスでもよい）

パスを構成する頂点のつまらなさの総和を最小化せよ。

解法

結局各辺に向きをつける問題となる。
高さに差がある頂点間の辺は、パスの向きが自明なので容易。
問題は、高さが同じ頂点間を結ぶ辺である。
a→b←cと辺を張るのと、a→b→cと張るのでは、bのカウント回数が変わりつまらなさの総和が変化する。

そこで、木DPの際、親に向け有向辺を張る場合と、親から子に向けて有向辺を張る場合を考え、それぞれSubTree内のつまらなさの総和を最小化しよう。

int N;
ll T[202020],H[202020];
vector<int> E[202020];

ll dp[202020][2];

void dfs(int cur,int pre) {
	int in=0,out=0;
	ll ret=0;
	vector<ll> dif;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		if(H[e]>H[cur]) {
			out++;
			ret+=dp[e][0];
		}
		else if(H[cur]>H[e]) {
			in++;
			ret+=dp[e][1];
		}
		else {
			out++;
			ret+=dp[e][0];
			dif.push_back(dp[e][1]-dp[e][0]);
		}
	}
	
	sort(ALL(dif));
	dp[cur][0]=dp[cur][1]=1LL<<60;
	for(int num=0;num<=dif.size();num++) {
		
		if(cur==0) {
			dp[cur][0]=min(dp[cur][0],ret+T[cur]*max(in,out));
		}
		else {
			if(H[cur]>=H[pre]) {
				dp[cur][0]=min(dp[cur][0],ret+T[cur]*max(in+1,out));
			}
			if(H[pre]>=H[cur]) {
				dp[cur][1]=min(dp[cur][1],ret+T[cur]*max(in,out+1));
			}
			
		}
		//cout<<cur<<" "<<in<<" "<<out<<" "<<dp[cur][0]<<" "<<dp[cur][1]<<endl;
		if(num<dif.size()) {
			out--;
			in++;
			ret+=dif[num];
		}
	}
	
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i];
	FOR(i,N) cin>>H[i];
	FOR(i,N-1) {
		cin>>x>>y;
		x--,y--;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	dfs(0,0);
	cout<<dp[0][0]<<endl;
	
}

まとめ

1750ptか。