求高手现身....

seven

求路过的大哥大姐大妈大叔萝莉御姐女王水王大圣给下这题的思路 ， 小弟将不胜感激涕零Orz加内牛满面中
8 F5 i" P1 P  h) `9 ~; [" _1 ^
Problem Description

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.
( g# J5 R8 g) IThe 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.

7 m1 |) r8 P& s& r3 D& l- l
, i6 N0 N1 A2 \7 V7 ]

Input

There are multiple test cases. For every test case, the first line has three integers, n, L and R (1<=n<=500000, 0<=L, R<=1000000000). The next n-1 lines each has three integers a, b and c, indicating that there is an edge going from spot a to spot b with length c (1<=c<=1000). The spots are labeled from 0 to n-1.
There is a blank line after each test case.
Proceed to the end of file.


" R# ^) v4 j8 p! l8 t

Output
: Y0 f: F4 v! {1 V
# j  P+ }! }4 E, |. P' K/ pIf 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.


. q  `# \8 ~1 {
Sample Input
$ I! g( s7 z3 A! `, o  }: ]1 Y  B
/ e2 ]  N; _" z- o! Q/ ]3 2 40 1 10 2 57 2 80 1 10 2 11 3 11 4 102 5 12 6 57 4 80 1 10 2 11 3 11 4 22 5 12 6 54 2 60 1 11 2 11 3 5


3 \( A; Z) ]$ \

2 ?; d% |: t% U0 E9 w5 gSample Output

* _8 M, h& T8 @" P5 b1 F. B# gOh, my god!262
" s4 |& L  s) T* s6 c! V
$ C" C* x* r' }' y

時間飛了

四级没过 路过

zhanglove0214

汗六级考了四次

magaera

哪位翻译下呢？

ice.beckham

一个男孩和一个女孩去买彩票

Shaman

哥是ACM高手，哥来帮你一把

Shaman

A和B出去耍，A喜欢走最短的路线，B喜欢走最长的路线。他们所要走的路线是一个棵树，结点表示他们要参观的景点，边表示两结点的间距。他们都从根结点出发，轮流选择对自己有利的路线（A选最短的，B选最长的）。下图是按SAMPLE2的数据作出的图，作为例子讲解一下：A和B同时从根结点0出发，由B先选路线；路线长度为红色数字，由于景点0到景点1和景点2的距离都一样（为1），所以B为了选择最长路线，必须要考虑到下一步的情况：如果B选线路0－1，则一下步A就有两种选择：1－3和1－4，距离分别是1和10；如果B选线路0－2，则一下步A就有两种选择：2－5和2－6，距离分别是1和5；由于A会选择最短的路线，所以两种情况其实是一样的，A都会选距离为1的路线。

1 D2 l/ D6 o3 M因此，在这个SAMPLE下，无论B最先选那个路线，总距离都是2.其它情况楼主就自己分析吧
+ A  f, y0 @& u$ S5 J8 U" X

' O6 _% n+ U8 r0 u* u# T( f: J. U

infinity1985

3 2 4 (n,L,R)表示：有三个点，走行距离2<=s<=4;
" {. Y; B# T* r. e7 Y7 H& |0 1 1 (a,b,c) 表示：点“0”到点“1”的距离为1
0 2 5 (a,b,c)表示：点“0”到点“2“的距离为5；
  B# Z" k/ f1 }  }, y- g1 ]1 T而所给路径只有“0”到“1”和“0”到“2”，走行距离或者为1或为5，都不符合要求。
行程为1，刚BOB不接受；
& W/ k: F  ]7 ]行程为5，则ALICE不接受；
而只有这二种方案，所以他们达不成一致意见。
$ z4 A* z" l9 j; i
3 x, \. n* g% D& {最优方案是在[L,R]区间内，选择走行距离最短的。

ice.beckham

A和B出去耍，A喜欢走最短的路线，B喜欢走最长的路线。他们所要走的路线是一个棵树，结点表示他们要参观的景 ...
Shaman 发表于 2010-9-30 09:31

$ ~; U' ^+ H& l6 d
" Z; v7 g9 g# U/ ?0 k
* q& Z! d) |2 D8 o    高手是你所

ice.beckham

A和B出去耍，A喜欢走最短的路线，B喜欢走最长的路线。他们所要走的路线是一个棵树，结点表示他们要参观的景 ...
2 S5 X1 u1 B2 T. @) Q" N8 ^Shaman 发表于 2010-9-30 09:31

5 g, t* q. I7 k5 ~

上厕所都不带纸的