Kisu Pari Na 2 (UVa 12437 World Finals Warmup 2012 1)
問題
頂点数Nの森が与えられる。K個の頂点を訪れるのに何回辺を通る必要があるか聞くクエリがq個来るので全て捌け。
1<=N,K,q<=10000
解法
前処理として連結成分ごとに分解して木の直径と頂点数を求める。各クエリに対してはK以上の頂点数を持ち、木の直径が最も大きい連結成分を使うのが最適になる。また直径をhとすると答えは2*K-min(h,K)-1となるので、各クエリをO(1)で処理することが可能。