---
lang: ja-jp
tags: APIO
---
# APIO 2020-C 楽しいツアー (Fun Tour)

方針を切り替える部分をよく考えずにやると痛い目を見る

## 問題文

https://apio2020.toki.id/assets/statements/fun_ja.pdf
https://oj.uz/problem/view/APIO20_fun

$N$ 頂点の木が隠されている。各頂点の次数は高々 $3$ である。木の情報は $2$ 種類のクエリにより与えられる。

- 頂点 $X,Y$ 間の距離
- 頂点 $X$ を根としたときの頂点 $Y$ の部分木のサイズ

$0, 1, \dots, N - 1$ の順列 $P$ であって、$\mathrm{dist}(P[i-1], P[i]) ≥ \mathrm{dist}(P[i], P[i+1])$ であるものを $Q = 4 \times 10^5$ 回以下のクエリで発見せよ。

$N ≤ 10^5$

## 考察

$Q \approx 4N$ であるから、線形っぽい。$4N$ 回以内で解きたい。
最遠点を取り続けると答えになる。
とすると直径？だけどクエリ回数が足りない
じゃあ重心？
重心は適当に根をとって部分木のサイズが半分以上で最小なところで求められる。
重心を必ず通るようにパスを取っていけば、重心からの距離の和で $2$ 頂点間の距離を求めることができる。
重心を取り除いた連結成分は半分以下になるから、はじめは重心を通って最遠点へを繰り返し、限界まで偏ったら 多い→遠い→多い→遠い→ のループで良い感じにできる。
$N$ 回で重心を求め、$N$ 回で重心からの距離を求められるが、どの頂点がどの連結成分に属するかがわからない。
次数は高々 $3$ なので、重心からの距離が $1$ の頂点について、重心より近いかどうか調べることで、どの連結成分に属するかが分かる ($3$ 個目の隣接点は調べなくて良いため、クエリは $2N$ 回)
これで、$4N$ 回で答えが求められることがわかった。

## 実装

限界が来るまで遠い点を取り、限界が来たら 多い→遠い→多い→遠い→ のループに入るを素直にやると、 遠→中(限界が来る)→近→遠 で困る。
そこで、限界が来る 1 つ前で一番遠い点を取っていたら多いループに入るようにする。

https://oj.uz/submission/367278

#include <bits/stdc++.h>
using namespace std;
 
int hoursRequired(int X, int Y);
 
int attractionsBehind(int X, int Y);
 
vector<int> createFunTour(int N, int Q) {
    vector<int> siz(N);
    for(int i = 0; i < N; i++) siz[i] = attractionsBehind(0, i);
    auto comp = [&](int x, int y){ if((x * 2 > N) ^ (y * 2 > N)) return x > y; return x < y; };
    const int cen = min_element(siz.begin(), siz.end(), comp) - siz.begin();
    vector<int> dist(N);
    for(int i = 0; i < N; i++) dist[i] = hoursRequired(cen, i);
    vector<int> dir;
    for(int i = 0; i < N; i++) if(dist[i] == 1) dir.push_back(i);
    vector<vector<int>> a(3);
    for(int i = 0; i < N; i++) if(i != cen) for(int j = 0; j < 3; j++) if(j == 2 || hoursRequired(dir[j], i) < dist[i]){
        a[j].push_back(i);
        break;
    }
    for(auto& v : a) sort(v.begin(), v.end(), [&](int x, int y){ return dist[x] < dist[y]; });
    sort(a.begin(), a.end(), [](auto& a, auto& b){ return a.size() > b.size(); });
    int last = -1;
    vector<int> ans;
    auto push = [&](int i){
        ans.push_back(a[i].back());
        a[i].pop_back();
        last = i;
    };
    while(a[0].size() && a[1].size() && a[2].size()) [&]{
        for(int i = 0; i < 3; i++) if(a[i].size() > a[(i + 1) % 3].size() + a[(i + 2) % 3].size()) return push(i);
        if(ans.empty() || all_of(a.begin(), a.end(), [&](auto& v){ return dist[ans.back()] >= dist[v.back()]; })){
            for(int i = 0; i < 3; i++) if(last != i && a[i].size() == a[(i + 1) % 3].size() + a[(i + 2) % 3].size()) return push(i);
        }
        const int i = max((last + 1) % 3, (last + 2) % 3, [&](int x, int y){ return dist[a[x].back()] < dist[a[y].back()]; });
        push(i);
    }();
    while(a[0].size() || a[1].size() || a[2].size()){
        const int i = [&](int x, int y){
            if(a[x].empty()) return y;
            if(a[y].empty()) return x;
            if(dist[a[x].back()] < dist[a[y].back()]) return y;
            return x;
        }((last + 1) % 3, (last + 2) % 3);
        push(i);
    }
    ans.push_back(cen);
    return ans;
}