ABC148 F - Playing Tag on Tree
問題
考察
先手が進める場所が1つで、そこに後手がいる場合には答えは0です。以下はそれ以外の場合を考えます。
以下の戦略対が最適です。
先手が必ず到達できて、後手からの距離が最大であるような葉の隣の頂点を$ tとする。
先手の戦略P: $ tに最短手順で逃げこんだ後、葉と往復し続ける
後手の戦略Q: 常にその時点で先手のいる側に動く
証明
頂点$ i, j間の距離を$ d(i,j)とします。
後手が戦略Qをとった場合
後手の手の後には必ず先手後手間の距離が1減ります。
先手の手によって先手後手間の距離は、+1か-1されます
木なので距離が同じ頂点に移動することはできません。
+1する回数を$ n_+、-1する回数を$ n_-とします。
距離が0になったときが終了なので、$ n_-は定数です。
$ d(u,v)が偶数なら$ d(u,v) = 2n_-(後手番で終了)
奇数なら$ d(u,v) = 2n_- -1(先手番で終了)
ゲーム終了まで後手の手数数は
$ d(u,v)が偶数なら$ n_+ + n_-
$ d(u,v)が奇数なら$ n_+ + n_- - 1
$ n_-は定数なので先手は$ n_+を最大化すればよいということになります。
頂点$ wでゲームが終了するとします。
$ N > 2では葉でゲームが終了することはないので、$ wは葉でないとします。
$ n_+ - n_- = d(w, LCA(u, w)) - d(u, LCA(u, w)) = d(v,w) - d(u,v)で、$ d(u,v)は定数なので結局$ d(v,w)を最大化すればよいということになり、このとき$ wは$ tになります。
したがって後手が戦略Qをとったときの先手の最適な戦略はPです。
また、このとき
$ d(u,v)が偶数なら$ n_+ + n_- = n_+ - n_- + 2n_+ = d(v,t) - d(u,v) + d(u,v) = d(v,t)
$ d(u,v)が奇数なら$ n_+ + n_- - 1 = n_+ - n_- + 2n_+ - 1 = d(v,t) - d(u,v) + d(u,v) = d(v,t)
で後手の手数数は$ d(v,t)となります。
先手が戦略Pをとった場合
このとき、ゲーム終了までが最も短くなるのは後手が$ tへ最短で移動する場合で、このとき後手の手数は$ d(v, t)です。
以上よりP, Qが最適な戦略対であることがわかりました。
アルゴリズム
$ u, $ vそれぞれから各頂点への距離をBFSで出します。
先手が到達できる頂点$ wは$ d(u,w) < d(v,w)
その中で最も$ d(v, w)が大きいもの-1が答えです。
時間計算量は$ O(N)です。
実装
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int N, u, v, M;
vector<vector<int>> G;
vector<int> bfs(int u) {
vector<int> d(N, -1);
queue<int> q;
q.push(u);
while (!q.empty()) {
int v = q.front();
q.pop();
q.push(w);
}
}
return d;
}
int main() {
cin >> N >> u >> v;
--u, --v;
G.resize(N);
rep(i, N - 1) {
int A, B;
cin >> A >> B;
--A, --B;
}
vector<int> dT = bfs(u), dA = bfs(v);
if (Gu.size() == 1 && Gu0 == v) { cout << 0 << endl;
return 0;
}
int ans = 0;
rep(i, N) {
if (dTi < dAi) ans = max(ans, dAi - 1); }
cout << ans << endl;
return 0;
}
参考