hdu4918 (树分治的维护)

题意:

一棵树,每个点有点权w,q次操作

1.将点x的点权修改为y 

2.问离x距离不超过d的点权和

 

思路:

将树分治中的计算部分需要的树状数组提出来,维护这个树状数组,每次查询修改均为O(log2n)

 

NOI2014购票(树的cdq分治+凸壳)

题目链接:

http://uoj.ac/problem/7

 

思路:

如果没有距离限制L的话只要dfs一遍同时维护到根的凸壳就可以(二分位置后可以做到O(1)添加,O(1)恢复)。

这题有个距离限制的话就可以将重心下面的点按d[v]-l[v]排序后,与重心到根的点一起双指针更新。