問題概要

$N$ 頂点からなる木が与えられる。 $i (1 \leq i \leq N-1)$ 番目の辺は $a_i$ と $b_i$ を結んでいる。

最初それぞれの頂点にコインが $1$ 枚おいてある。高橋くんと青木くんはそれぞれコインが置いてある頂点 $v$ を $1$ つ選びその頂点に置いてあるコインをすべて取り，そのあとすべてのコインを $v$ に距離 $1$ だけ近づけるという操作を繰り返す。

操作ができなくなった人を負けとすると，お互いに最善を尽くしたときどちらが勝つかを求めよ。

(問題文は https://atcoder.jp/contests/agc033/tasks/agc033_c に記載されている。)

制約

$1 \leq N \leq 2\times 10^5$
$1 \leq a_i \leq N (1 \leq i \leq N-1)$
$1 \leq b_i \leq N (1 \leq i \leq N-1)$
$a_i \neq b_i$
与えられるグラフは木

アイディア

$1$ 回の操作でコインは選んだ頂点 $v$ に少しずつ引き寄せられるので，葉となる頂点からはコインは出ていくが入ってこない。つまり， $1$ 回の操作はグラフから葉となる頂点をすべて消す(ただし選んだ頂点 $v$ については葉であっても当然消されない)のと同値である。

ここで，木上の最長パスのうちの $1$ つ(このパスを $P$ とする)についてのみ考えることとする。この最長パスの端点を $S, T$ とすると $S$ か $T$ を選ぶとこのパスの長さは $1$ 減り， $S, T$ 以外の頂点を選んだ場合についてはこのパスの長さは $2$ 減ることになる。

次に， $P$ 上にない頂点について考える。葉ではない頂点を選ぶとき，すべての葉が消されるので， $P$ よりも長いパスができることはなく， $P$ のパスを $2$ 減らすこととなる。また， $S, T$ のどちらかを選ぶときも同様に $S, T$ のうち選ばれなかった頂点とすべての葉が消されるので， $P$ よりも長いパスができることはなく， $P$ のパスを $1$ 減らすこととなる。

さらに， $P$ 上にない葉を消すことを考えると，もしもその葉が $P$ とは別の最長パスの端点であったとしたらそのパスを新たに $P$ として考えることができ(つまり $P$ の長さが $1$ だけ減る)，それ以外のときは $P$ より長いパスができることはないので結局 $P$ のパスを $2$ 減らすこととなる。

以上のことから，1回の操作は $P$ の長さを $1$ または $2$ 減らすことと同値であることが分かる。

実装

木の最長パスを一般に直径という。直径の長さ(及びその長さを持つパス)はどの頂点でもよいので頂点を1つ選び $V$ とし， $V$ から最も遠い頂点の $1$ つを $S$ として， $S$ からもっとも遠い頂点の $1$ つを $T$ とすると， $S$ と $T$ を端点とするパスの長さと一致する。 $S$ と $T$ は簡単なBFSで求められるので，直径の長さは $O(N)$ で求まる。

そして，直径の長さをもとに青木くんが勝つか高橋くんが勝つかは単純なメモ化再帰 *1で求めることができる。この計算量は $O(N)$ である。

よって全体的な計算量は $O(N)$ である。

コード

#include <iostream>
#include <vector>
using namespace std;

const int INF = (1<<30);

vector<int> g[225816],q[2];
int dist[225816];
bool done[225816],memo[225816];

bool solve(int r){
    if(done[r]){
        return memo[r];
    }
    done[r] = true;
    if(r==0){
        memo[r] = true;
    }else if(r==1){
        memo[r] = false;
    }else{
        memo[r] = (!(solve(r-1)&&solve(r-2)));
    }
    return memo[r];
}

int main(void){
    int N,a,b,i,j,k;
    cin >> N;
    for(i=1; i<N; ++i){
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    a = 0;
    for(k=0; k<2; ++k){
        fill(dist,dist+N,INF);
        q[k].push_back(a);
        dist[a] = 0;
        for(i=0; i<q[k].size(); ++i){
            a = q[k][i];
            for(j=0; j<g[a].size(); ++j){
                b = g[a][j];
                if(dist[b] > dist[a]+1){
                    dist[b] = dist[a]+1;
                    q[k].push_back(b);
                }
            }
        }
    }
    cout << ((solve(dist[a]))?"First":"Second") << endl;
    return 0;
}

(提出したものはこちら)