本文主要是介绍noip——关于树的总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2018年信息学奥赛NOIP资料下载
这几年考了好几次树上问题：
NOIP2012 疫情控制(二分答案+倍增+贪心)
NOIP2013 货车运输(最大生成树+倍增)
NOIP2014 联合权值(勉强算作树形dp的傻逼题)
NOIP2015 运输计划(二分答案+树上差分+最近公共祖先)
NOIP2016 天天爱跑步(树上差分+树上倍增)
可以说除了联合权值外都有一定的难度，(关键是我不抄题解一道也做不出来)
去年没考树上的问题所以我感觉今年要考
树
树是一种极其优美的结构，树上两点之间有且仅有一条路径。
在近年来oi中常出现关于树的题目。
树的直径
树的直径就是树中最长的一条路径，处理方法有树形dp和两遍dfs或bfs
需要注意的是在存在负边权的树中只能用树形dp来求直径
1.巡逻
一道画画图就能搞出来的题。。。
首先我们应该想想他让我们修路有什么用。你随便画一棵树就很容易发现，要想从一个点出发经过所有点一遍再回来，每条边是要经过两次的。而我们修路就是为了让其中一些边只走一次。
K=1：显然我们随意连一条边会形成一个环，环上的边我们只用经过一次。这样我们最大化环的的长度就行，也就是找到树的直径。
K=2：首先我们肯定还是连直径。但是第二条边怎么连？显然我们还可以找次长链出来。但如果两条链有重叠怎么办？
我们可以把第一条链在算完长度后将所有边权赋成-1，这样就不会算重了。设两次选的边长度分别为l1,l2，那么答案就是2∗n−l1−l2。
2.消防
首先我们应该想到这条路径一定在树的直径上。这里给出证明：
设直径的长度为d，那么直径外的边长度一定小于等于d/2（否则该路径会与直径的一部分构成一条比直径还长的路径）
若该路径不在直径上，则直径的最远点到该路径的距离至少为d/2
而如果在直径上，一定存在一段路径使得树上所有点的距离到它不超过d/2
所以选在直径上一定是优的，而且在符合题目要求的情况下越长越好。
那么如果我们确定里直径，我们可以O(n)求出直径上每个点到最远点的距离，然后左右指针扫直径，单调队列维护区间最小值即可。
3.直径
求直径的长和直径并的数量。
直径当然好求，而直径并，一定是在一条直径上。
所以我们可以先求出一条最长链。而所有直径的并一定是最长链上连续的一段。
证明很简单：如果中间有分开而最后又和在一起，显然会形成一个环。
然后我们对于最长链上的每个点，dfs求出其子树中距离最远的点，若两点之间的距离等于该点到直径一个端点的距离，那么显然这个点到端点之间这一段就不能用来统计答案了，将它们从答案中删除即可。
然后我们可以正着做一遍这个操作，反向再做一遍，中间没被删除部分即为直径的并
树上管理问题
树上的每个点能管理相邻一片区域，求最少几个点能管理整棵树。
一般考虑从下往上贪心。
1.救火站Gas
又是树上管理类的问题，我们当然考虑贪心。这个题算是消防站的设立那道题的加强版。
很显然的一种做法是对于一个点，我们要找一个深度最小的点来覆盖它。
然后看这个数据范围k<=20，我们可以想到把他当成状态放进数组里
设need[i][j]为以i为子树的j级子孙有几个未覆盖，left[i][j]为以i为子树的j级子孙有几个多出来控制的没使用
显然当need[i][j]中j=k时，我们就必须放消防站来管理了
然后我们还可以用left来抵消need
2.消防局的设立
有一种很显然的贪心测略：对于当前深度最大的点，我们选他的爷爷点一定是最优的。
对于最深的点我们选离他最远但是能管理到他的祖先即可。
树上倍增&&树上差分
这几年考过好几次树上倍增，有两次都是和树上差分结合在一起的。利用树上倍增求出两点的LCA，然后两点(u,v)之间边的信息往往可以转化为(u−>root)+(v−>root)−2∗(LCA−>root)，点的信息可以转化为(u−>root)+(v−>root)−LCA−>root−faLCA−>root。
1.天天爱跑步
对于每一条链，我们根据套路把他拆成(u−>root)+(v−>root)−LCA−>root−faLCA−>root
然后我们发现(u−>root)和(v−>root)要分别处理(因为一个往上走一个往下走)
设观察员y出现的时间为wy
那么x向上跑要想被观察员看见，就要满足等式deepx−wy=deepy，移项得到deepx=deepy+wy，换句话说，y子树内只有满足deepx=deepy+wy的点会对y产生贡献
当x向下跑想被y看见，我们可以设x的时间为edx，根据刚才的套路，我们发现子树内只有满足deepx−edx=deepy−edy的点会对y产生贡献
用一个桶dfs一遍即可求出答案，是不是越想越简单了。。
2.运输计划
根据套路最大值最小的问题我们考虑二分，假设我们二分出来的答案为mid，那么我们显然要把大于mid的所有计划减去同一条边，且这条边在大于mid的计划的路径并上
我们差分一下求出每个计划对路径的覆盖，只有覆盖数目等于大于mid的计划的边可以考虑被减去
对这些可以减去的边取一个最大值然后判断即可
以前感觉这道题很神仙，其实仔细一分析每一步都是套路
3.疫情控制
仔细分析题目，好像还是最大值最小啊，当然是考虑二分咯。显然我们在军队没跳到首都之下的儿子上时，一直往上跳是最优的
但调到首都儿子上时，我们发现一个问题，如果接着往上跳，很可能在这个点重新需要控制的时候就跳不回来了，那还不如不跳
所以我们把所有调到首都后能返回他上一个儿子的点全部跳到首都，对于子树内的所有叶子已经被覆盖的军队当然也跳到首都，因为再留在这个点已经没有意义了
然后我们在首都枚举所有的叶子，如果还没被覆盖，就从首都派遣军队进行覆盖，如果所有军队都到不了叶子的祖宗，自然二分的答案不合法
这篇关于noip——关于树的总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
