下午树图基本应用基础

树和图的基础应用JiangsuHuaiyinVocationalandTechnicalSchoolzcysky什么是树和图？一种数据的组织处理方式线性表->树->图是从特殊到一般的关系。为啥要学这些东西呢？因为NOIP要考也是为学习高级数据结构等打下基础。我们会讲什么？树：（我们假设大家都会存储以及dfs遍历）树的一些概念：重心，直径。树上节点的最近公共祖先（LCA）。最近公共祖先的应用。我们会讲什么？图：（假设各位同学已经掌握图的存储，遍历）图的最短路径算法图的最短路径算法活用图的最小生成树算法拓扑排序树的一些基础性质一对多的关系，一个父亲有多个孩子。层次性，递归定义。边数=点数-1树上两点之间路径唯一，不存在环。树的一些奇奇怪怪的东西树的重心。什么是树的重心呢？就是如果选择一个点作为这棵树的根节点，可以使得剩下的部分相对较小。（也就是大小接近）可以用来干嘛呢？比如树的分治算法。如何求树的重心呢？重心的性质：性质1：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，到他们的距离和一样。性质2：把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。性质3：一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。解法：运用重心的性质那么找到一颗树的重心有以下算法：（1）dfs一次，算出以每个点为根的子树大小。（2）记录以每个结点为根的最大子树的大小。（3）判断：如果以当前结点为根的最大子树大小比当前根更优，更新当前根。一些树的重心的例题POJ1655题意:给定一棵树,求树的重心的编号以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的.树的重心裸题。树的直径树的直径是什么呢？就是树上最长的一条树链。直径我们怎么求呢？方法1：动态规划我们直接求这个最长链似乎并不是很简单，但是如果我们枚举树上一个点，可以发现经过这个点的最长链一定是由从这个节点出发向子树的最长链+不在同一个子树的次长链组成。于是这个问题就可以随便dp解决了。方法二：dfs这里不给出严格证明，只是简单的理解一下：直径是一棵树上最长的一条树链。那么我们先求出到一个点最远的点。很显然，这条路径大概是这样：跑到直径，然后沿着直径到最后一个端点。这样我们就找到了直径的一个端点。在进行一遍同样的dfs，求出另一个端点，就知道了答案。两个算法的复杂度均为O(n)一个简单的题现给出一个树，以及每条边的权值，现在需要重新构建一个树，每条边的权值为原树上两点之间的距离。问权值之和最大为多少。先找出直径，然后再搜索出每个点分别到直径的两个端点的距离，求和并加上直径的长度即答案。最近公共祖先(LCA)什么是最近公共祖先呢？其实是一个很好懂的定义，就是从两个点一直向上走，第一个相遇的节点就是最近公共祖先。这个东西的用途很多，比如如下的这个例子。从一个小问题说起

给定一棵树，每次询问树上两个点之间的最短距离。直接从一个点开始bfs，直到找到目标点？或者使用例如spfa之类的最短路径算法？上述做法都是naive的。因为树不是一般的图，树有他自己的性质，强行忽略这些性质做题第一会带来很大的复杂度，第二也丧失了这种结构的优美性。分析性质前面讲过，树的边数=点数-1也就是说，树的点对之间路径是唯一的，只要不无聊去走重复的点，走到的路径肯定是唯一而且最短的（也就是所谓的简单路径）那么画一个图，我们发现路径的情况其实只有两种。记录下一个节点相对于根节点的深度d，那么回想之前的lca：我们发现第一种走法就是u->lca,lca->v.第二种走法就是u->v,但是lca(u,v)=v再考虑到每次其实是在走深度差，dis=d[u]+d[v]-2*d[lca]求法最一般的做法就是倍增，这个做法常数较大，但是非常直观易懂。考虑最简单的做法，就是一层一层往上提，就像我之前“定义”的一样。这种东西多半都可以通过倍增加速，每次提不会傻乎乎的提升1，而是用2的倍数。具体的实现可以参考代码讲，我认为倍增lca的代码非常直观。一种常数更小的求解方法之前的求解办法是每次跳2的幂次，保证了复杂度是O(logn)还有一种办法就是将树链进行划分，选取size最大的子树作为重儿子连成重链，每一段重链可以直接跳可以证明重链不会超过logn条，因此总复杂度依然是O(logn)但是和前者相比，一次预处理可以快速回答所有询问，而且常数非常优秀。树链剖分其实非常简单，但是是提高组内容，有兴趣的同学可以去看nzhtl1477老师的提高组讲课。LCA的简单应用例题P2912[USACO08OCT]牧场散步PastureWalking预处理到根结点的距离，然后直接按照之前的公式计算即可（我不会说示例的代码就是这题的）LCA的简单例题【bzoj1787】[Ahoi2008]Meet紧急集合求出三个点两两的lca，直接计算最优解即可。还有一种做法就是如果有两个lca相等，那么集合点就是下一个。图论图的一些性质：多对多没有太多性质了。树是一种特殊的图。图的最短路径最简单的算法：floyd算法，也是考纲内唯一的多源最短路径算法。算法的核心非常简单，枚举中间中转节点，暴力枚举完就完成了所有最短路的计算。图的最短路径有的最短路径问题是固定起点的，称为单源最短路。这类问题有三种算法：bellman-Ford,Dijkstra,SPFA其中第一种比较慢，第二种很不错但是不能出现负权，第三种复杂度比较玄学但是总体表现很快。我们讲一下Dijkstra算法和SPFA算法。Dijkstra算法这类最短路径算法的基础：三角形不等式。具体而言就是反复利用三角形不等式进行迭代，直到找到最优解的过程。这个我觉得照着讲义讲非常好~SPFA算法是一种优化过的Bellman-Ford算法。d[v]>=dis[u][v]所以d是单调不降的，这也是最短路径算法的基础。spfa的特点：只有当前被更新的点才对状态产生贡献，用队列维护所有有用状态。对着代码讲可能比较好。spfa的其他东西用dfs实现的spfa如果未被访问过直接dfs(v)即可。但是诚如上午所说，这类“最短”的问题，dfs存在一定的盲目性，所以dfs效率较差，无法通过luogu的模板数据。dfs-SPFA的应用可以用来快速的找负环。找到了可增广，并且已经在dfs栈里面的节点，证明找到了负环。那么bfs实现的spfa如何寻找负环呢？如果一个点进队次数达到n，证明它在一个负环里面。显然前者效率更为优秀。一些简单的应用2017计算之道复赛D.百度地图导航最小生成树算法一般而言最多人写的最小生成树是Kruskal，而且非常简单。前置技能：并查集。简单介绍算法原理：首先我们证明一个定理：边权最小的边肯定在最小生成树上。将他加入最小生成树。如果一条边连接的两个点已经被联通，那么这条边肯定不选，因为我们已经有了更优的方案。不断重复上述过程，直到我们得到了最小生成树。最小生成树的应用P2330[SCOI2005]繁忙的都市考虑Kruskal的性质，我们最后加入的边肯定是最大的，而且在所有可能方案中，它一定是最小的。所以直接Kruskal算一遍即可。拓扑排序啥是拓扑排序呢？先介绍DAG（有向无环图），这个自然是字面意思。每次选择入度为0的点，把它删掉，不断重复，直到删完了整张图，这就叫拓扑排序，得到的序列就是拓扑序。显然拓扑序不唯一拓扑排序的意义例子：选课。比如某些东西的学习顺序：想学习splay就得先学会二叉排序树，二叉排序树可以直接学，线段树可以直接学，想学会segment-tree-beats!就得先学会线段树，想学会Link-Cut-Tree就得先学会splay和树链剖分……我们发现事件（或者节点）之间存在着依赖关系，也就是我们必须按照一定的顺序做某些事情，这就是拓扑排序。拓扑排序的实现用bfs进行拓扑排序。先把入度=0的点全部压入队列，然后每次拓展，把新的ind[v]=0的点放入队列。对着代码讲。深入谈一些拓扑排序的性质拓扑排序与动态规划。动态规划的状态转移是要满足拓扑序转移的，本质上所有的动态规划是一边拓扑排序一边计算方案。树的拓扑序树是天生满足拓扑序的结构。很多树上问题的统计都是从下向上的，本质上是把树在进行拓扑排序。例题NOIP2013车站分级暴力拓扑排序，连边无法承