树分治：处理树上点对问题——点分治
树p的重心x：x为树p的重心<=>x为p中所有x的子树中最大的子树节点数最少的点（绕绕绕~）
树形dp O（n）可求
性质：
一个重心的各儿子代表的子树中最大的那棵子树的大小不会超过n/2。（n为重心所属树的节点数size）
—>每次找到一棵树的重心，将其删掉后对各个子树递归下去，递归深度为O(log n)
总结：
——树分治一般是处理点对问题，最终会把问题归结为经过根节点的满足条件的点对问题，这种问题的两种做法：
1、补集转化
2、根据题目建立对应的数据结构，每次枚举一棵子树，对子树里的每个元素查询一下，再将子树的每个元素插入进数据结构。
往往要根据题目对这两种方法进行相应的取舍。
——点分治结构 点分治树（遇到再说）
给定一棵有根树，有若干操作，分别为给一条链整体加一个值，查询一条链的最值
做法一：树链剖分
做法二：动态树
评论 (0)
