Kisu Pari Na 2 (UVa 12437 World Finals Warmup 2012 1)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3868

問題

頂点数Nの森が与えられる。K個の頂点を訪れるのに何回辺を通る必要があるか聞くクエリがq個来るので全て捌け。
1<=N,K,q<=10000

解法

前処理として連結成分ごとに分解して木の直径と頂点数を求める。各クエリに対してはK以上の頂点数を持ち、木の直径が最も大きい連結成分を使うのが最適になる。また直径をhとすると答えは2*K-min(h,K)-1となるので、各クエリをO(1)で処理することが可能。