DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 : D - 道路網

うーむ、これ系ぱっと思い浮かばないなぁ。
http://ddcc2016-qual.contest.atcoder.jp/tasks/ddcc_2016_qual_d

問題

N頂点の完全グラフがある。
うち(N-1)個の辺とその長さが与えられる。これらの辺によりN頂点は木を成している。
残りの辺の長さはすべて定数Xである。

2頂点の対における最短距離の総和を求めよ。

解法

まず、2頂点の距離は以下のように計算できる。例外事項もあるがそれはあとで処理する。

• 最初の(N-1)辺により距離X以下で接続できるなら、それが2点の距離。
• Xを超えてしまう場合、その他の辺を使うことで距離がXとなる。

分割統治法で上記を求めよう。
まず木の重心を求める。
そしてその重心を根とし、各子頂点についてSubTree中に登場する頂点までの距離を求め、その距離をとる頂点の数と総和を求め、それぞれBITで管理しよう。
ある子頂点のsubtreeにおける頂点vの距離がD(v)である場合、他のsubtreeの頂点wに対しD(v)+D(w)＞XならX、D(v)+D(w)≦XならD(v)+D(w)で移動できる。
前述の2つのBITを使うと、各wに対しmin(X,D(v)+D(w))の総和を高速に処理できる。
各subtreeの処理を完了したら重心を削除し、また各子頂点のSubtreeに対し再帰的に重心を求めていけばよい。

1つ問題が残っていて、2頂点(V,W)の距離がXを超えてしまう場合がある。
それはその頂点がXを超える辺で結ばれている場合。
その場合以下の最小値をとる。

• あきらめてV-W間の辺を使う
• Vの隣接頂点のうち最短距離の点に移動し、そこからXかけてWに移動
• Wの隣接頂点のうち最短距離の点に移動し、そこからXかけてVに移動
• VにもWにも隣接しない点Yがあれば、V-Y-Wと2Xかけて移動
• VにW以外の隣接点Yがあり、WにV以外の隣接点ZがああるならV-Z-Y-Wと3Xかけて移動

最後に上記の分を調整しよう。

int N;
ll X;
vector<pair<int,int>> E[101010];
int did[101010], NC[101010], mie[101010];
vector<int> add,addsum;
ll ret;
int center;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt_tot,bt_num;


void dfs(int cur,int pre,int num) {
	NC[cur]=1;
	FORR(e,E[cur]) if(e.first!=pre && did[e.first]==0) {
		dfs(e.first,cur,num);
		NC[cur]+=NC[e.first];
	}
	if(center==-1 && num-NC[cur]<num/2) center=cur;
}

void dfs2(int cur,int pre, int dep) {
	NC[cur]=1;
	dep=min(dep,101010);
	ll left=max(0LL,X-dep);
	ret += bt_tot(left)+bt_num(left)*dep+X*(addsum.size()-bt_num(left));
	add.push_back(dep);
	
	FORR(e,E[cur]) if(e.first!=pre && did[e.first]==0) {
		dfs2(e.first,cur,dep+e.second);
		NC[cur]+=NC[e.first];
	}
	
}


void gogo(int cur,int num) {
	if(num<=1) return;
	
	center=-1;
	dfs(cur,-1,num);
	if(center==-1) center=cur;
	
	FORR(e,E[center]) if(did[e.first]==0) {
		dfs2(e.first,center,e.second);
		FORR(a,add) {
			bt_tot.add(a,a);
			bt_num.add(a,1);
			addsum.push_back(a);
		}
		add.clear();
	}
	
	ret += bt_tot(X) + X*(addsum.size()-bt_num(X));
	
	FORR(r,addsum) {
		bt_tot.add(r,-r);
		bt_num.add(r,-1);
	}
	addsum.clear();
	
	did[center]=1;
	FORR(e,E[center]) if(did[e.first]==0) gogo(e.first,NC[e.first]);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) mie[i]=404040;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		x--;
		y--;
		E[x].push_back({y,r});
		E[y].push_back({x,r});
		mie[x]=min(mie[x],r);
		mie[y]=min(mie[y],r);
	}
	
	gogo(0,N);
	
	FOR(i,N) FORR(r,E[i]) {
		x=r.first;
		if(i>x) continue;
		if(r.second<=X) continue;
		ll mi=r.second;
		if(E[i].size()>1&&E[x].size()>1) mi=min(mi,3*X);
		if(E[i].size()+E[x].size()-1!=N-1) mi=min(mi,2*X);
		mi=min(mi,X+mie[i]);
		mi=min(mi,X+mie[x]);
		ret += mi-X;
	}
	
	cout<<ret<<endl;
}

問題

最後の隣接点の処理を見落としそう。