技術室奥プログラミングコンテスト E - 不可視境界線 (The Invisible Borderline)


E - 不可視境界線 (The Invisible Borderline)

問題概要

辺にコストがある木が与えられる。
各頂点から最も遠い点を求めよ。

考察

木の直径を用いて解を求めることを考えます。

f:id:noy72:20180111095259p:plain:w500

まず、最長パス p_0, p_1, p_2, ... , p_k を求めます。
赤い部分は最長パスに含まれることを表しています。

すると、最長パスに含まれる頂点と、最長パスに含まれない部分木に分けることができます。

最長パスに含まれる頂点 p_i の最遠点

p_0 から p_i までの距離と、 p_i から p_k の距離を比較すれば良いです。

部分木に含まれる頂点の最遠点

ある部分木 s_{p_i} に含まれる全ての頂点の最遠点は、 p_i の最遠点と一致します。
一致しないと仮定すると、最長パスであることと矛盾します。

  • 最長パスの一部を含まないようなパスよりも、含むパスの方が必ず長くなる。
  • 最長パスの一部を経由して別の部分木に入るようなパスよりも、入らないパスの方が必ず長くなる。


最遠点が複数ある場合は、頂点番号が小さいものを出力しなければいけないので、そこだけ注意します。

コード

※最長パスが複数ある場合を考えていないのにACしたコード

  1. bfsで最長パスを求める
  2. 最長パスに含まれている頂点の最遠点を求める
  3. 部分木を求める
  4. 部分技に含まれる頂点の解を求める
  5. 出力
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

#define int long long
const int INF = (1LL << 60);

const int MAX_V = 100005;

class Edge{
	public:
		int to, dis;
		Edge(){}
		Edge(int to, int dis): to(to), dis(dis)  {}
};

vector<Edge> g[MAX_V];
int dis[MAX_V];

vector<int> bfs(int s, int n, bool f){
	queue<int> q;

	rep(i,n) dis[i] = INF;
	dis[s] = 0;
	q.push(s);

	vector<int> pre(n,-1);
	while(not q.empty()){
		int d = q.front(); q.pop();

		rep(i,g[d].size()){
			Edge e = g[d][i];
			if(dis[e.to] == INF){
				pre[e.to] = d;
				dis[e.to] = dis[d] + e.dis;
				q.push(e.to);
			}
		}
	}

	int maxi = -1;
	rep(i,n){
		if(dis[i] == INF) continue;
		if(maxi == -1) maxi = i;
		if(dis[maxi] < dis[i]){
			maxi = i;
		}
	}
	if(f) return vector<int>() = {maxi};

	vector<int> path = {maxi};
	while(pre[maxi] != -1){
		maxi = pre[maxi];
		path.emplace_back(maxi);
	}
	reverse(all(path));
	return path;
}

//---------------------------- union-find
int par[MAX_V]; //親
int depth[MAX_V];//木の深さ

void init(int n){
	rep(i,n){
		par[i] = i;
		depth[i] = 0;
	}
}

int find(int x){
	if(par[x] == x){
		return x;
	}else {
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(depth[x] < depth[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(depth[x] == depth[y]) depth[x]++;
	}
}

bool same(int x, int y){
	return find(x) == find(y);
}
//----------------------------

signed main(){
	int n;
	cin >> n;

	vector<pair<int, int>> e(n - 1);
	rep(i,n - 1){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		e[i] = make_pair(a,b);
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
	}

	vector<int> path = bfs(bfs(0, n, 1).front(), n, 0); //最長パスを求める
	vector<bool> used(n,0);
	vector<int> ans(n);
	for(auto i : path){
		used[i] = true;
		if(dis[i] > dis[path.back()] - dis[i]){
			ans[i] = path.front();
		}else if(dis[i] < dis[path.back()] - dis[i]){
			ans[i] = path.back();
		}else{
			ans[i] = min(path.front(), path.back());
		}
	}

	init(n);
	rep(i,n - 1){ //部分木を求める
		if(used[e[i].first] and used[e[i].second]) continue;
		unite(e[i].first, e[i].second);
	}

	vector<int> par(n);
	for(auto i : path){
		par[find(i)] = ans[i];
	}
	rep(i,n){
		if(used[i]) continue;
		ans[i] = par[find(i)];
	}

	for(auto& i : ans){
		cout << i + 1 << endl;
	}
}