uva 1484 - Alice and Bob's Trip（樹形dp）

題目大意：alice和bob小兩口一起出去旅行，他們從0城市出發，bob喜歡走比較遠的路，因為他是個勤奮的好孩子，alice喜歡走比較近的路，因為她是一個不勤奮的壞孩子，是以有了意見上的分歧，于是乎在出門前他們約法三章，要求說最後的距離值在[l,r]之間，并且由夫妻兩輪流做決定，決定說下一個城市去哪裡。現在給出n個城市，以及n-1條邊，問說在不讓bob媳婦生氣的情況下，bob最遠能走多遠（不違反約定），如果無法做到不違反約定的話，輸出oh，my

god！

解題思路：樹形dp，其實有點像暴力，每個節點其實隻會計算一次（樹狀結構，n-1條邊，并且保證聯通）；

也就是說在題目給出圖的時候，就已經确定說各個點所位于的層數，奇數層的肯定是bob決定，偶數層的肯定是alice決定。于是在每層計算的時候，有一個x值表示是奇數層還是偶數層，用于确定說是誰在做決定，如果是bob，肯定選擇最大的，如果是alice肯定選擇最小的，但是不管是誰，都要保證說不能違反約定，那麼就不能将層與層之間完全分離計算距離，s為跟蹤的距離值，用于判斷是否違反約定。