Alice and Bob's Trip (UVa Live Archive Asia - 2010 Harbin)
問題
頂点数nの木の上で二人で旅行のルートを決める。旅行のルートの長さは[L,R}以内に入ってなければならない。アリスは条件をみたす中で最短の物を選びたがり、ボブは最長の物を選びたがる。ボブから初めて二人交互に辺を一つずつ選んでいくとすると旅行の長さはいくらになるか?
1<=n<=500000
0<=L<=R<=1000000000
葉に到達するかどの辺を選んでも条件を満たさなくなる場合はそこで終了する。
解法
条件を満たさないものは無視しながらMinMax法をするだけ。