いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Grand Contest 001 C - Shorten Diameter

解法

木の直径の性質を考えると,どの点からの距離も直径をkとするとのk/2になる点があるような気持ちになる(厳密ではない)
厳密には直径が偶数の場合は全ての点からの距離がk/2以下になる点が
奇数の場合は(k-1)/2になる”辺”が
それぞれ存在する
そのような点または辺を探してそれぞれk/2,(k-1)/2を超える点の数を数えればいい
点または辺は全探索しても間に合うのでO(n^2)で通る

Submission #2904096 - AtCoder Grand Contest 001