Problem E. Alice and Bob's Trip
时间限制 2000 ms
内存限制 32 MB
Alice and Bob are going on a trip. Alice is a lazy girl who wants to minimize the total travelling distance, while Bob as an active boy wants to maximize it. At the same time, they cannot let the value to be less than a given integer L since that will make them miss too much pleasure, and they cannot let the value to be greater than a given integer R since they don't want to get too exhausted.
The city they are visiting has n spots and the spots are connected by directed edges. The spots are connected in such a way that they form a tree and the root will always be at spot 0. They take turns to select which edge to go. Both of them choose optimally. Bob will go first.
输入数据
输出数据
If the total distance is not within the range [L, R], print "Oh, my god!" on a single line. Otherwise, print the most value Bob can get.
样例输入
复制
3 2 4
0 1 1
0 2 5
7 2 8
0 1 1
0 2 1
1 3 1
1 4 10
2 5 1
2 6 5
7 4 8
0 1 1
0 2 1
1 3 1
1 4 2
2 5 1
2 6 5
4 2 6
0 1 1
1 2 1
1 3 5
样例输出
$ Mathjax font initiator $