北京游记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. 模拟退火