《有关树的算法》PPT课件

《《有关树的算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树胜利一中王子昱概要定义&性质树的遍历Dfs序,Bfs序&欧拉序LCA问题树形DP*树分治题目选讲定义&性质定义(之一):联通、无环的无向简单图每个顶点都是割点，每条边都是割边NOI07追捕盗贼在树上添加一条边会得到一个环在生成树相关的问题中很有用的性质树是二分图关键字N个顶点，n-1条边的联通图任意两点间有且只有一条路径每个点向东至多连一条边([NOI2008]道路设计)Etcetera树的遍历深度优先遍历和图的dfs一致先序遍历，中序遍历，后序遍历……DFS序DFS序深度优先遍历得到的序列:

2、Dfs(x)list.push_back(x)Foreverychildchofx:Dfs(ch)List.push_back(x)记录第一次访问和最后一次访问abeeffbcgghhiicdjjda((()())(()()())(()))DFS序::性质一棵子树对应一段连续的序列abeeffbcgghhiicdjjda或者是abefcghidja例题给定一棵节点带权的树两种操作AIdelta：以I为根的子树内节点权值+deltaQI:求以I为根的子树的权值和树状数组

3、线段树维护dfs序abee

4、ffbcgghhiicdjjda((()())(()()())(()))DFS序::性质改动一下刚才的代码:Dfs(x)list.push_back(+x)Foreverychildchofx:Dfs(ch)List.push_back(-x)考虑这个序列从+a到+g的和+a+b+e–e+f–f–b+c+g正负抵消后就是从a到g的路径！abeeffbcgghhiicdjjda((()())(()()())(()))例题一棵节点带权的树，两种操作AIdelta:点i的权增加deltaQIj:输出从

5、i到j的路径上点的权值和直接套用刚才的方法？abeeffbcgghhiicdjjda((()())(()()())(()))例题反例：从e到c+e–e–b+ce->ca->e+a->c–weight[a](+a+b+e)+(+a+b+e–e+f–f–b+c)–aQ(u,v)=Q(w,u)+Q(w,v)–weight[w],W=LCA(u,v)什么是LCA？一会再说……树状数组

6、线段树维护DFS序abeeffbcgghhiicdjjda((()())(()()())(()))广度优先遍历图的B

7、FS使用队列BFS序BFS序广度优先遍历得到的序列Bfs(x)Que.push(x)WhilenotQue.empty()Y=que.pop()List.push_back(y)Foreverychildchofyque.push(ch)同一深度的节点形成一个连续的区间AlgorithmEngagement2010Firm这道题涉及的一些东西超纲了==abcdefghij欧拉序列以根为起点的欧拉回路应用：LCA(最近公共祖先)问题：LCA(u,v)表示u和v的深度最大的公共祖先图中LCA(g,h

8、)=c，LCA(g,j)=a给欧拉序列里的每个点加权，点i的权值是i的深度于是u,v的LCA是欧拉序列中u,v之间深度最小的点证明？abebfbacgchcicadjdae.g.abebfbacgchcicadjda0121210121212101210LCA(g,h)=c树形DPSPOJPT07X树的最小覆盖最小覆盖：选出点集的最小子集使得每条边至少有一个端点在该点集中二分图：转化为匹配f1[i]表示选择i时,以i为根的子树的最小覆盖;f0[i]表示不选i时的最小覆盖转移SPOJPT07Z树的

9、最长路一种优美的贪心算法两遍dfs应用了树的独特性质,不可推广DP任意选定一个根最长路一定是从一个点向下扩展出的最长路f[]和次长路g[]（如果有）的和只需要维护这两个量就可以了最长路::推广求出每个顶点出发的最长路定根之后，计算出从每个点向下的最长路f[]和次长路g[]点u的最长路可能是直接向下的(f[u])，也可能是向上之后再向下(设为h[u])怎么计算H[]？最长路::推广树形DP的推广不一定是在树上进行的DpSDOI2010Area题意：最大权独立集30%数据：图是一棵树Dp70%数据：

10、图是基环+外向树的结构如果只有环该怎么做？100%数据：仙人掌树形DP大多数题目的套路是一样的自底向上自顶向下在状态中维护额外的信息点分治题目选讲树网的核[NOIP2007,modified]给定一棵边带权的树，求出一条长<=W的路径，使得到路径距离最大的点的距离最小N<=300000Next树网的核[Hint]证明：最优方案可以是直径的一段直径的优美性质Next树网的核[Solution]求出直径对直径上的点，计算disLeft[x]=x左端所有结点到x距离的最大值disRight[x]同类d