树的相关算法定义n树：要么为空，要么由根结点(root)和n棵子 树组成。n森林：若干棵树n二叉树：递归定义n要么为空，要么由根结点左子树和右子树组成n左右子树都是一颗二叉树如何分辨树n关键词n任意两点有且只有一条路径nN个点M条边的连通图 M0则代 表ans还可以变得更大，否则就缩小二分的 ans，直到二分到足够的精度为止。图的生成树n次小生成树n若数据范围较小，可以先求出最小生成树，每 次去掉最小生成树上的一条边，再求一遍最小 生成树，即为次小生成树。n实现简单，时间复杂度较高。图的生成树n次小生成树n首先求出原图最小生成树，记录权值之和为 MinST。枚举添加每条不在最小生成树上的边 (u,v)，加上以后一定会形成一个环。找到环上 权值第二大的边(即除了(u,v)以外的权值最大的 边)，把它删掉，计算当前生成树的权值之和。 取所有枚举修改的生成树权值之和的最小值， 就是次小生成树。 图的生成树n对图深度优先搜索，定义DFS(u)为u在搜索树（以 下简称为树）中被遍历到的次序号。定义Low(u) 为u或u的子树中能通过非父子边追溯到的最早的 节点，即DFS序号最小的节点。根据定义，则有 ：nLow(u)=Min DFS(u) DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)bfsn非比赛时可使用编译开关nPascal $m 100000000nC+ #pragma comment(linker,“/STACK:65777216“)树形数据结构n并查集n处理一些不相交集合（Disjoint Sets）的合并及 查询问题 n路径压缩n团伙n有N个人，M个关系，M个关系中每对X和Y可 以是敌人也可以是团伙，是敌人的话，那么敌 人的敌人也是团伙。问最多有多少个团伙。n星球大战n一个无向图，有以下两种操作n删去某个点以及其所有关联的边n询问图中有多少联通块树形数据结构n排序二叉树n多关键字n会退化n已知升序的N个数以及他们的各自需要被访 问的次数，要求建立一个最优排序二叉树 使得总的访问代价最小。一个结点的访问 代价=深度访问次数。noptij 枚举根进行转移n可用四边形不等式优化树形数据结构n二叉堆n完全二叉树n注意边界ndijkstra+heap,prim+heapnA,B分别为两个单调不减的数列，求所有的 Ai*Bj中第K小的项。(N,K=100000)nK路归并会做不？n有一篇凹凸不平的矩形地面，面积为m*n， 被分为M*N个小正方形，每个正方形有不 同的高度，给出矩形中每个正方形的高度 ，若一场雨后，这块矩形地面最多能积多 少体积的水。树形数据结构n线段树n插入（删除）操作的时间复杂度为O (Log N)。 nLazy 操作n数轴上有很多条线段，数轴上的每个位置 都有一个容量，表示这个位置最多能被几 条线段覆盖，求能在数轴上最多放置多少 条线段。(所有数=100000)树型动态规划n给定一棵树求树上最长路n在树上的一些点放置士兵，每个士兵能监 视到的点是自己所在的点和他相邻的点， 求最少放置多少士兵能监视到树上所有的 点。n在树上的一些边放置士兵，每个士兵能监 视到的点是他所在的边连接的两个点，求 最少放置多少士兵能监视到树上所有的点 。n一棵树，选取一个点当中心的代价是树上 每个点到这个点的距离之和，求选取一个 点使代价最小。n选课n学校开设了N（N300）门的选修课程，每门 课程都有一个学费Wi，每个学生可选课程的数 量M是给定的。在选修课程中，有些课程可以 直接选修，有些课程需要一定的基础知识，必 须在选了其它的一些课程的基础上才能选修。 你的任务是为自己确定一个选课方案，使得你 能得到的学分最多，并且必须满足先修课优先 的原则。假定课程之间不存在时间上的冲突。n状态转移方程nFI,J=MAXFT,K+FI,J-Kn(0=K=J-1,TSONI); n事实上,我们可以做到O(N2)的优化：考虑一个结点的子 结点要么选要么不选，不妨就假定它的子结点一定选，这 时候就可以让它带着父结点的最优值加上本身价值继续下一层更新，递归返回时只需比较FT,J与FI,J+1即可。 nProcedure treedp(I)n For X1 TO SONI,0n T=SONI,Xn For J0 TO M-1 FT,J=FI,J+WTn treedp(T)n For J0 TO M-1n FI,J+1=MAX(FI,J+1,FT,J)n树与二叉树的转化n左儿子右兄弟表示法n这样的好处是在很多树形动态规划问题中 能大大降低编程复杂度和算法的时间复杂 度没了