技術室奥プログラミングコンテスト 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;
}
}