[problemUrl]: https://atcoder.jp/contests/apc001/tasks/apc001_e $ N $ 頂点の木があります。頂点には $ 0 $ から $ N\ -\ 1 $ まで番号が振られています。また、$ i $ ($ 0\ <\ =\ i\ <\ N\ -\ 1 $) 番目の辺は頂点 $ a_i $ と $ b_i $ を結んでいます。各頂点対 $ u $, $ v $ ($ 0\ <\ =\ u,\ v\ <\ N $) に対して、距離 $ d(u,\ v) $ を「パス $ u $-$ v $ に含まれる辺の本数」と定義します。近い将来、いずれか $ 1 $ 個の頂点に宇宙人が襲来することが予想されています。すぬけ君は、宇宙人が襲来したときにその頂点をすぐに特定したいと考えています。そのために、あらかじめいくつかの頂点にアンテナを設置しておくことにしました。まず、アンテナの個数 $ K $ ($ 1\ <\ =\ K\ <\ =\ N $) を自由に決めます。そして、すべて相異なる $ K $ 個の頂点 $ x_0 $, $ x_1 $, ..., $ x_{K\ -\ 1} $ を自由に選び、各頂点にアンテナ $ 0 $, $ 1 $, ..., $ K\ -\ 1 $ を設置します。頂点 $ v $ に宇宙人が襲来すると、アンテナ $ k $ ($ 0\ <\ =\ k\ <\ K $) は距離 $ d(x_k,\ v) $ を出力します。すぬけ君は、これら $ K $ 個の出力結果をもとに、宇宙人が襲来した頂点を特定します。よって、どの頂点に宇宙人が襲来してもその頂点を一意に特定するためには、次の条件が成り立つ必要があります。 - 各頂点 $ u $ ($ 0\ <\ =\ u\ <\ N $) に対してベクトル $ (d(x_0,\ u),\ ...,\ d(x_{K\ -\ 1},\ u)) $ を考えたとき、これら $ N $ 通りのベクトルはすべて相異なる。条件を満たすようにアンテナを設置するとき、アンテナの個数 $ K $ の最小値を求めてください。

AT_apc001_e Antennas on Tree

Description

Input Format

Output Format

Explanation/Hint