求问有没有神牛写了noi2014题解。

树链剖分。线段树的每个节点就维护当前区间的凸包。

某d2t3的若干做法。
解法1：
链上有l限制？就是询问区间凸包，我们上sdoi2014 向量集 那题的线段树维护凸包即可。
树上？树链剖分套这个做法。
nlg^3n，注意常数可以过。
解法2：
(听vfk扯了一会自己yy的。。不知道和vfk的做法是不是差不多)
链上有限制？询问区间凸包？cdq分治！
树上就上点分治！
链上树上都是nlg^2n
解法3:
树上无l限制怎么办？
dfs，维护一个“函数式”单调栈。插入用二分。
有l限制？
开线段树，每个节点一个“函数式”单调栈！
nlg^2n。

感觉太含糊。。稍微讲一下分治吧
f_i即i号点的答案。
考虑链上有l限制的情况。
分治可以用一下伪代码描述。。
solve(l,r)
solve(l,mid)
用[l,mid]的信息来更新[mid+1,r]的f_i。
solve(mid+1,r)
考虑如何更新[mid+1,r]的f_i。
大概是说。。当链上有l限制的时候。
对于每个点i，能更新它答案的点是一个区间。不妨设为[l_i,i-1]
(右端点显然是i-1)
然后我们考虑如何高校地用[l,mid]的信息来更新[mid+1,r]的f_i。。
假设[mid+1,r]里面的所有点。。都按照 可行区间左端点l_i从大到小排序。。
然后我们维护一个指针now。。
按左端点从大到小的顺序枚举[mid+1,r]里面的点，假设当前枚举到i。。
(初始now=mid)
然后while(now>=l_i) 将(dis_now,f_now)加入单调栈中。。(就是单调栈维护凸壳)
在单调栈二分计算出f_i。。
这样子我们就能在nlg^2n的时间里面用分治解决了链上的l有限制的问题。。
树上的做法。。套用这个上点分治！
点分治大概就是这样说。。
对于一个有根树。。
先找出它的重心。。
拿掉这个重心，这棵树会被分裂为一堆联通块。
然后把深度最浅的那个连通块。。(根节点所在的连通块)。。
递归计算f_i。
接下来考虑除根节点所在子树之外的子树
我们用根节点所在子树的信息来更新除根节点所在子树之外的子树的dp值。。
很显然。
根节点连通块能更新除根节点所在子树之外的子树的节点只有根到重心路径上的点。
我们还是套用类似链状的那种分治方法。。
然后对于非根节点连通块的话。我们分治的时候把根设定为与重心相连的那个点，然后把这个子树看作有根树继续分治下去就行了