技術室奥プログラミングコンテスト E - 不可視境界線 (The Invisible Borderline)
E - 不可視境界線 (The Invisible Borderline)
問題概要
辺にコストがある木が与えられる。
各頂点から最も遠い点を求めよ。
考察
木の直径を用いて解を求めることを考えます。
まず、最長パス を求めます。
赤い部分は最長パスに含まれることを表しています。
すると、最長パスに含まれる頂点と、最長パスに含まれない部分木に分けることができます。
最長パスに含まれる頂点 の最遠点
から までの距離と、 から の距離を比較すれば良いです。
部分木に含まれる頂点の最遠点
ある部分木 に含まれる全ての頂点の最遠点は、 の最遠点と一致します。
一致しないと仮定すると、最長パスであることと矛盾します。
- 最長パスの一部を含まないようなパスよりも、含むパスの方が必ず長くなる。
- 最長パスの一部を経由して別の部分木に入るようなパスよりも、入らないパスの方が必ず長くなる。
最遠点が複数ある場合は、頂点番号が小さいものを出力しなければいけないので、そこだけ注意します。
コード
※最長パスが複数ある場合を考えていないのにACしたコード
- bfsで最長パスを求める
- 最長パスに含まれている頂点の最遠点を求める
- 部分木を求める
- 部分技に含まれる頂点の解を求める
- 出力
#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; } }