Codeforces #525 Div2 F. Ehab and a weird weight formula

考察さえできれば実装は容易。
https://codeforces.com/contest/1088/problem/F

問題

木を成すグラフが与えられる。
各頂点vにはコストC(v)が設定されている。
なお、コストには以下の特性がある。

• コストの最小値を持つ頂点は１つである
• 上記頂点以外は、必ず１つ以上自身より小さいコストの点が隣接している

この木の辺を張り替え、別の全域木を作ることを考える。
この全域木のコストは以下の総和とする。

• 頂点vの次数がdeg(v)とすると、v*deg(v)
• 頂点u,v間に辺を張る場合、dist(u,v)を元のグラフにおける頂点間の最短距離としてceil(log(dist(u,v)))*min(C(u),C(v))

コストの最小値を求めよ。

解法

以下の２つの特性が重要である。

• このグラフをコスト最小値の点を根と考えると、必ず親頂点の方がコストが低い状態になる。
• 頂点u,vを連結すると、上記２種類のコストを合わせて(ceil(1+log(dist(u,v)))*min(C(u),C(v)) + max(C(u),C(v)))だけ全域木のコストに加算される

ここから、以下の考察が得られる。

• コスト最小値以外の点vは、元グラフで祖先に位置する点uのいずれかに接続するのが良い。

祖先以外側に近づくほどmin(C(u),C(v))が小さくなるので、祖先以外の頂点につなぐとmin(C(u),C(v))は大きくなるわdist(u,v)は大きくなるわで意味がない。

そこで、DFSで根から順に接続先を決めていこう。
根から順にコストを並べた配列を管理しながらDFSする。
ceil(1+log(dist(u,v))が一致する祖先の頂点間では、根に近いものほど(ceil(1+log(dist(u,v)))*min(C(u),C(v))が小さくなる。
よって頂点vから、1,2,4,8...個親側の頂点とのコストを総当たりでチェックすればよい。

int N;
int W[505050];
vector<int> E[505050];
int D[505050];
ll ret;

void dfs(int cur,int d) {
	D[d]=W[cur];
	
	ll mi=1LL<<40;
	for(int i=0;i<=20;i++) {
		int td=max(0,d-(1<<i));
		mi=min(mi,D[td]*(i+1LL));
	}
	if(d) ret+=mi+W[cur];
	
	FORR(e,E[cur]) if(W[e]>W[cur]) dfs(e,d+1);
	
}

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

まとめ

本番正答者が少なかったので、やっぱり考察が若干難しい問題ってことだね。