CSAcademy Round #84 : E. Growing Trees

これは解けてもよかったなぁ…。
https://csacademy.com/contest/round-84/task/growing-trees/

問題

木を成すN頂点の無向グラフが与えられる。
各辺にはコストが割り振られており、経過時間に線形で変化する。負になることもある。

直径、すなわちグラフ内における頂点間の最短経路のコストの最大値が負になる時間とそのときの直径を求めよ。

解法

頂点間のコストは、線形で変化するコストの総和なのでやはり時間に線形である。
ただ、これはO(N^2)通り存在するので総当たりはできない。

しかし、O(N^2)通りも線形の関数があっても、その最大値は下に凸となる。
よって、時間を三分探索すればよい。

int N,D;
int C[252525],A[252525];
vector<pair<int,int>> E[252525];
ll ret[1010101];

ll dfs(int cur,int pre,int v) {
	vector<ll> cand;
	cand.push_back(0);
	cand.push_back(0);
	FORR(e,E[cur]) if(e.first!=pre) {
		cand.push_back(dfs(e.first,cur,v)+C[e.second]+v*A[e.second]);
	}
	sort(ALL(cand));
	reverse(ALL(cand));
	ret[v]=max(ret[v],cand[0]+cand[1]);
	return cand[0];
}

ll hoge(int v) {
	if(ret[v]==1LL<<60) {
		ret[v]=0;
		dfs(0,-1,v);
	}
	return ret[v];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	
	FOR(i,N-1) {
		cin>>x>>y>>C[i]>>A[i];
		E[x-1].push_back({y-1,i});
		E[y-1].push_back({x-1,i});
	}
	FOR(i,D+1) ret[i]=1LL<<60;
	
	int L=0,R=D;
	while(L<R-3) {
		int M1=(L*2+R)/3;
		int M2=(L+R*2)/3;
		ll v1=hoge(M1);
		ll v2=hoge(M2);
		if(v1<=v2) R=M2;
		else L=M1;
	}
	
	ll mi=1LL<<60;
	for(i=L;i<=R;i++) mi=min(mi,hoge(i));
	for(i=L;i<=R;i++) if(ret[i]==mi) {
		cout<<i<<endl;
		cout<<mi<<endl;
		break;
	}
}

まとめ

たくさん線形関数があるときの最大値・最小値は凸になるという性質を忘れていた…。
本番Convex Hull Trickをこねくりまわしてしまった。