Playing Tag on Tree [AtCoder Beginner Contest 148 F]

https://atcoder.jp/contests/abc148/tasks/abc148_f

解説

https://atcoder.jp/contests/abc148/submissions/9103846

色々考えることができそう。
以下解法は全探索しているが、色々なことを要求しているので、木へのライブラリを余り持ってない場合は、
ちょっと理解するに難しいかもしれない。

何か全探索できないだろうか。
性質として、青木くんは、なるべく高橋くんに接近するように動くのが良さそう。
つまり、高橋くんの移動ルートが決まれば青木くんの行動は一意に定まることになる。
なので、全探索すべきは高橋くんの行動であることになる。

高橋くんは最終的には追い詰められるわけで、木で追い詰められる所というと葉になる。
なので、全ての葉に対して高橋くんが目指した時にゲームが終了する回数を数えて最大のものが答えになる。
高橋くんがある葉に移動するときに、まず、その葉に到達できる可能性を考えてみる。
これは、高橋くんと青木くんが同時にその葉に向かったときに、パスが合流する頂点に高橋くんが1ターン先に
到達できる場合である。
同じターンに到達すると、高橋くん移動→青木くん移動となって、だめ。
この頂点を効率良く求めるには、LCAを使用する。
葉は毎回変わるが、高橋くんと青木くんは変わらない。
よって、高橋くんを根として、葉と青木くんのLCAを取る。
すると、合流地点が分かる。
（どこを根にしても問題ないかも）
各頂点間の距離はDFSしておけば、LCAと組み合わせることで計算可能。
自分はこの辺の木ライブラリを1つにまとめて上手いことしてあるので、ペタっと貼るだけ。

最後は青木んと葉の距離-高橋くんと葉の距離をdとしたときに、
d=1なら0, d=2なら1, d=3なら2, d=4なら3, d=5なら4, d=6なら5という感じなのでd-1だけ移動することになる。

int N, u, v;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> u >> v;
    u--; v--;

    HLDecomposition hld(N);
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        hld.add(a, b);
    }
    hld.build(u);

    int ans = 0;
    rep(leaf, 0, N) if (hld.g[leaf].size() == 1) {
        int lc = hld.lca(leaf, v);

        int taka = hld.distance(lc, u);
        int aoki = hld.distance(lc, v);

        if (aoki <= taka) continue;
        
        int taka2 = hld.distance(u, leaf);
        int aoki2 = hld.distance(v, leaf);

        int cnt = taka2;

        int d = aoki2 - taka2;
        cnt += d - 1;
        chmax(ans, cnt);
    }
    cout << ans << endl;
}