F - Playing Tag on Tree

問題

頂点の木が与えられる。木上の頂点に2つコマを置き、これらについて、次のゲームを行う.
・各ターンごとに、をこの順序に従って隣接する頂点に移動させる.ただし、一つの頂点に2つ以上のコマが存在するとき、ゲームを終了する
・はできるだけゲームを長く続けるように最適に移動し、はゲームをできるだけ早く終了するように最適に移動する。
・ の移動回数を求めよ.

解法

できるだけ長く移動するコマの最適な移動方法よりも、できるだけ早く終了させる最適なコマの動かし方()は容易にわかるので、そこから考える.
・はに向かって最短距離で進めば良い。
次に、の動かし方について考える.
上記の考察に基づき、からできるだけ遠い頂点に, より早く到達できれば良い。
したがって、それぞれのコマを根としたときの到達ターン数を各頂点について計算し、が早く到達できる頂点について必要ターン数計算し、その最大値を答えとすれば良い。
注意点として、ある頂点に2つのコマが到達する最短距離が等しいときは、その距離が1の場合はそのまま処理すれば良いが、それ以外の場合は、それが答えとはならないので適当に流せば良い。

感想

・木じゃないとめちゃくちゃめんどくさそうだなと思った
・LCAでも解ける(?)らしいので今度やる
・ブログの更新が遅くなると広告がではじめるらしいので、頑張りたい

#include <bits/stdc++.h>
using namespace std;
using Int = long long;
constexpr Int inf = 1e9;
void dfs(int v,vector<int>&d,vector<vector<int>>&edge){
    for(auto nv : edge[v])
        if(d[nv] == inf) d[nv] = d[v] + 1, dfs(nv,d,edge);
}
int main(){
    int N, u,v;
    cin >> N >> u >> v;
    --u; --v;
    vector<vector<int>>edge(N);
    for(int i = 0; i + 1 < edge.size(); ++i){
        int s,t; cin >> s >> t;
        --s; --t;
        edge[s].emplace_back(t);
        edge[t].emplace_back(s);
    }
    vector<int>td(N,inf), ad(N,inf);
    td[u] = 0; ad[v] = 0;
    dfs(u,td,edge); dfs(v,ad,edge);
    int ans = 0;
    for(int ed = 0; ed < N; ++ed){
        int tmp = 0;
        if(td[ed] == ad[ed]){
            tmp = 1;
        } else if(td[ed] > ad[ed]){
            continue;
        } else {
            tmp = max(td[ed],ad[ed]) - 1;
        }
        ans = max(ans,tmp);
    }
    cout << ans << endl;
}