问题在于规模,这么大的规模,显然是O(N)才能通过的.分为两步来做,第一步是求所有点的最远距离.树状DP求,down[i]表示以i为根的子树的最大深度,top[i]表示从i点向上的最远距离,然后借助父亲节点和孩子节点可以比较容易地O(n)时间内求出.然后,题目变成了一个数列,寻找一段最长的连续的部分,满足里面最大的元素减去最小的元素<=m.数列为a[i],维护两个队列，min 和 max ，都是存的下标，min[i]<min[i+1] , max[i]<max[i+1] ,且a[min[i]]<a[min[i+1]], a[max[i]]>a[max[i+1]],然后从小到大枚举区间的右边界,枚举以后就更新两个队列,更新完以后取出min和max的头节点进行检查 ,如果a[max[1]]-a[min[1]]<=m，那么符合要求，更新答案。如果不满足，那么将min[head1]和max[head2]中那个较前面的元素踢掉,再次检查,直到满足条件.每个元素进出两个队列一次，O(N) 

• Re:真觉得中文亲切，原来没看懂……>_< (0) byron 2006-12-31 18:26:39
• 传说每个点的最远点对Tree DP需要维护三个状态值~~ (2) dut200901102 2011-03-24 12:28:37