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为跟踪的距离值，用于判断是否违反约定。