北京游记Day4

树分治

1.分治

1. 分治要求

   1. 问题缩小到一定规模是就可以容易的解决

   2. 该问题可以分解为若干个规模较小的相同问题，即用最优子结构的性质

   3. 利用该问题分解出的子问题的解可以合并为该问题的解

   4. 该问题所分解的各个子问题是相互独立的，不包含公共子问题

2. 树

1. 树的定义

   没有环的连通图

2. 性质

   1. 去掉树的一条边后所得的图不连通

   2. 在树中添加一条边后所得的图一定存在环

   3. 每一对顶点U V间有且仅有一条路径

3. 点分治

1. 基本方法

   首先选取一个点将无根树转为有根树，在递归处理每一颗以根节点的儿子为根的子树

2. 例题

   1. POJ1741

      求树上距离小于等于K的点对有多少 (N<=10000)

       点分治+DP
      

   2. BZOJ2599

4. 边分治

1. 基本方法

   自己YY

2. 例题

   1. QTREE4
      或BZOJ1095(题意相同)

5. 基于链的分治(树链剖分)

1. 题目：[Query On a Tree]

略

1. Astar2008 黑白树

2. QTREE4

6. 基于询问的分治 (CDQ分治)

1. BZOJ2001

7. 模拟退火