Codeforces #600 Div2 F. Cheap Robot

6問ある回としては簡単かも。
https://codeforces.com/contest/1253/problem/F

問題

木を成すグラフが与えられる。
辺にはコストが設定されている。

この木をロボットが移動することを考える。
ロボットが辺を移動するには、コスト以上の燃料がなければならず、移動するとコスト分燃料が減る。
木のうちいくつか指定された頂点では、燃料を初期値に回復することができる。

2頂点A,Bで指定されるクエリが与えられる。いずれも、燃料を初期値に回復できる点である。
A→Bに移動するときの必要燃料初期値の最小値を答えよ。
なお、A→Bは直行せず寄り道してもよい。

解法

まず元のグラフで、各点を最寄りの体力回復点でグループ化しよう。
このグループを点とみなし、グループをまたぐ辺のみを残したグラフを考える。
体力回復点X,Yに対し、それぞれに属する点X',Y'が隣接している場合、グループ間の移動距離はX-Yの距離ということになる。

クエリの解は、Aに対応するグループからBに対応するグループにおける変型後のグラフの辺のコストの最大値となる。
この状態では寄り道は不要なので、LCAとダブリングを用いてコストの最大値を求めよう。

int N,M,K,Q;
vector<pair<int,int>> E[101010];
vector<pair<int,ll>> E2[101010];
int from[101010];
ll dist[101010];

int P[21][200005],D[200005];
ll ma[21][200005];


template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

void dfs(int cur) {
	FORR(e,E2[cur]) if(e.first!=P[0][cur]) {
		D[e.first]=D[cur]+1;
		P[0][e.first]=cur;
		ma[0][e.first]=e.second;
		dfs(e.first);
	}
}
int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d%d",&N,&M,&K,&Q);
	FOR(i,M) {
		scanf("%d%d%d",&x,&y,&r);
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	priority_queue<pair<ll,int>> PQ;
	FOR(i,N) {
		if(i<K) from[i]=i, PQ.push({0,i});
		else dist[i]=1LL<<60;
	}
	
	while(PQ.size()) {
		ll co=-PQ.top().first;
		int cur=PQ.top().second;
		PQ.pop();
		if(dist[cur]!=co) continue;
		FORR(e,E[cur]) if(dist[e.first]>co+e.second) {
			dist[e.first]=co+e.second;
			from[e.first]=from[cur];
			PQ.push({-dist[e.first],e.first});
		}
	}
	
	vector<vector<ll>> Es;
	FOR(i,N) FORR(e,E[i]) if(from[e.first]>from[i]) {
		Es.push_back({dist[i]+dist[e.first]+e.second,from[i],from[e.first]});
	}
	sort(ALL(Es));
	FORR(e,Es) {
		if(uf[e[1]]!=uf[e[2]]) {
			uf(e[1],e[2]);
			E2[e[1]].push_back({e[2],e[0]});
			E2[e[2]].push_back({e[1],e[0]});
		}
	}
	dfs(0);
	FOR(i,19) FOR(x,K) {
		P[i+1][x]=P[i][P[i][x]];
		ma[i+1][x]=max(ma[i][x],ma[i][P[i][x]]);
	}
	while(Q--) {
		scanf("%d%d",&x,&y);
		x--;
		y--;
		int lc=lca(x,y);
		ll ret=0;
		for(i=18;i>=0;i--) {
			if(D[x]-D[lc]>=1<<i) ret=max(ret,ma[i][x]), x=P[i][x];
			if(D[y]-D[lc]>=1<<i) ret=max(ret,ma[i][y]), y=P[i][y];
		}
		cout<<ret<<endl;
	}
	
	
	
}

まとめ

コードは長いけど考えはさほど難しくない。