树的重心与直径

树的直径

定义

树的直径指树的简单最长路

求法

两遍DFS，第一遍任取一点，找一个与这个点距离最远的点，可以证明这个点一定是直径的一个端点；第二遍从这个端点出发，找到离这个端点距离最远的点，这个点即为直径的另外一个端点。

例题1

  • [Description]
    给定一棵树，在树上任意放置三个点ABC，求路径A-B-C的最大值。
  • [Solution]
    可以看出，A-B或B-C一定有一条是树的直径（不然可以调整到更优），所以找出树的直径后，枚举另外一个点的位置即可，3遍DFS解决。

例题2 [BZOJ1912] APIO2010patrol

  • [Description]
    求边权为1的树的最长链和不为最长链子链的次长链。
  • [Solution]
    最长链就是树的直径咯，求出直径后，把直径上边的权值变为-1，即对答案的贡献为-1，再求一遍直径即可。

树的重心

定义

使得去掉这个点后最大联通分块最小的点。

意义

删掉后子树尽量平衡，在树分治的时候避免极端退化情况。

性质

  • 以重心为根，所有子树的大小不超过树的大小的一半
  • 树中所有点到某个点的距离和中，重心为最小（默认边权为1）
  • 用一条边连接两棵树，新树的重心在原来两棵树重心之间的路径上
  • 删掉或添加一个叶子结点，树的重心最多只会移动一条边

(感觉可以出很多恶心题了)

动态维护

【先等我学完LCT

模板题 [POJ1655]

树的分治

点分治

在无根树中选取一个结点作为根进行操作，再递归处理它的子树。
对于点分治，若每次选取树的重心，可控制复杂度在O(logn)O(logn)之内（所有子树大小都不会超过原树一半）。

例题1 [POJ1741] Tree

例题2 [SPOJ FTOUR2] Free tour II

  • [Description]
    给定一棵含有N 个结点的带权树，其中结点分为两类，黑点和白点。要求找到一条路径，使得经过的黑点数不超过KK个，且路径长度最大。
  • [Solution]
    要用到平衡树，之后再来看。】

边分治

选取一条边，将树分为两个不相交的部分，再递归处理这两棵树。
对于点分治可控制复杂度在O(logn)O(logn)之内，而对于边分治，最坏情况下可能达到O(n)O(n)，很少采用。

复杂度的改进

对于边分治，通过像点分治那样改变选边标准是没有作用的，因为最坏情况下无论选哪条边都是一样，那我们可以通过重构图来做到把每个点的度数控制到常数范围内。
之后讲解树链剖分例题2的时候会提到。

链分治 - 树链剖分

解决的问题

在一棵树上进行如下操作：两点间路径上边权的修改/求极值/求和。

方法

如果是对数组进行操作，我们可直接用线段树来完成，然而边并不是线性的，树链剖分就是把维护对象从复杂的树形结构，转化简单的线性结构。
树链，指树上的路径；剖分，指将路径划分为重链和轻链。
给出几个定义：
重儿子：结点的一个子树最大的儿子 / 轻儿子：除了重儿子的其余儿子
重边：结点与重儿子间的连边 / 轻边：结点与轻儿子间的连边
重链：由重边连成的路径 / 轻链：由轻边连成的路径
这样划分，有如下性质：

  • 每个点属于且仅属于一条重路径
  • 轻儿子的子树大小不大于原树大小的1/2
  • 结点到根的路径上轻边和重链的个数都不超过log(n)log(n)
    其中第三条由第二条推出（想一想，为什么）。
    这样，通过维护轻边或者重链来维护整条路径，就能将原本O(n)O(n)的复杂度降到O(logn)O(logn)
    此时我们需要给边在线段树中编号，而且使得同一条重链中所有边在线段树中的编号是连续的。怎么做到呢？我们通过两遍DFS来实现。
    第一遍，算出所有结点的fa,h_son,dep,order(父亲，重儿子，深度，子树大小)，这个简单，不再赘述。
    第二遍，算出所有结点的top,num(结点所在链的顶端的边，此边在线段树中的编号)，方法是优先遍历第一遍求出的重儿子，重边的编号当然就在一起啦！
    那我们怎么将路径u-v上所有轻边和重边一起找出来并处理呢？帅的人有这段代码。
1
2
3
4
5
6
7
8
9
10
11
12
int work(int u,int v){
	int ans=0,tp1=top[u],tp2=top[v];
	while(tp1!=tp2){
		if(dep[tp1]<dep[tp2]){ swap(u,v); swap(tp1,tp2); }
		ans=max(ans,query(num[tp1],num[u],0));
		u=fa[tp1],tp1=top[u];
	}
	if(u==v) return ans;
	if(dep[u]>dep[v]) swap(u,v);				//在一条重链上
	ans=max(ans,query(num[son[u]],num[v]));
	return ans;
}

以上就是树剖的全部内容。

与树的分治的关系

我们发现，点的分治是每次删除一个点，边的分治是一次删除一边，而树链剖分，是在路径上一次删除一条链，我们可以说这是链的分治，而复杂度同样也有保证。

模板题 [SPOJ375] QTree

例题1 黑白树

  • [Description]
    你拥有一棵有n个结点白色的树——初始所有节点都是白色的。
    接下来，你需要处理m条指令：
    1.修改指令：改变一个给定结点的颜色（白变黑，黑变白）；
    2.查询指令：询问从结点1 到一个给定结点的路径上第一个黑色结点编号。
  • [Hint]
    n,m≤106n,m≤10^6
  • [Solution]
    仍然是在链上的操作，只不过维护对象变成了点，那能不能用树剖呢？当然可以。我们把给边标号改成按dfs序给点标号就好了。

例题2 [SPOJ2666] Query On a Tree

  • [Description]
    给定一棵包含n个结点的树，每个节点要么是黑色，要么是白色。要求模拟两种操作：
  1. 改变某个结点的颜色
  2. 询问最远的两个黑色结点之间的距离
  • [Hint]
    n≤105,−1000≤边权≤1000n≤10^5,−1000≤边权≤1000
  • [Solution]
    【正在写】

例题3 [NOIP2013] 货车运输

  • [Description]
    给定一个n个点，m条边的无向图，求图上任意两点间路径上边权的最小值，若不存在路径路径则输出-1，q组询问。
  • [Hint]
    n≤105,m≤5×105,q≤3×105.n≤10^5,m≤5×10^5,q≤3×10^5.
  • [Solution]
    最大生成树+树链剖分（因为不涉及边权修改，树上倍增也是不错的选择）模板题。

总结

在算法的常数方面，树的路径剖分算法是当中常数最小的算法，基于点的分治其次，基于边的分治常数较大。
在算法的应用范围方面，基于链的分治与基于点(边)的分治有所不同。前者的特点在于每次被删除结点的儿子必将作为下一次删除的链的头结点，这一点是基于点(边)的分治无法达到的。所以前者可以用来维护路径上的点(边)，但如果维护的对象是路径的长度，后者的能力更强。
与基于点的分治比较，基于边的分治在设计高效算法的思考难度上明显小于前者。
这几个算法各有所长，需要我们根据具体情况，灵活运用，以最佳的方式解决题目。

treap

概述

treap，顾名思义，就是 tree+heap.
treap是一种平衡树，每个节点有两个值value和priority，根据value满足二叉搜索树的性质，同时根据priority满足堆的性质。value是固有的，priority的值是rand()随机出来的，这样保证树的期望深度为log(n).
操作与BST类似，再用左旋或右旋来维护堆的性质。

支持的操作

（默认为小根堆）

插入

先按BST插入结点，再进行如下操作直到满足要求为止：若priority值比父节点小，为左儿子则进行右旋，否则左旋，重复操作到比父节点大为止。

查找(存在性/极值)

同BST.

修改

// 同BST.

删除(给定值/极值)

先查找到位置，若为叶子则直接删除，否则为左儿子则左旋，否则右旋，直到变成叶结点为止。

分离

在需要分离的地方插入一个节点，将其旋至根再删除，左右两个子树就是分离出来的两个treap.

合并

与分离互为逆运算，需满足其中一个treap的值都小于另外一个treap的结点的值。
添加一个根，将两棵树作为左右子树，再删除根即可。

splay

概述

splay也是一种平衡树，虽然速度略慢于treap，但能力是要大于treap的，例题里会提到。
splay也是通过左旋(zig)和右旋(zag)来使得平衡，它行动的出发点是要把被操作的点选至根，可以证明，每次操作的复杂度均摊下来为log(n).

支持的操作

（有自底向上的splay和自顶向下的splay，这里以自底向上为准）

伸展

将结点旋至根，若当前不为根，不断分为如下情况进行操作：
若父节点为根，为左儿子就右旋(zag)，否则左旋(zig)。
若结点为左儿子，父节点为左儿子，连续进行两次右旋(zag-zag)
若结点为右儿子，父节点为右儿子，连续进行两次左旋(zig-zig)
若结点为右儿子，父节点为左儿子，先左旋再右旋(zig-zag)
若结点为左儿子，父节点为右儿子，先右旋再左旋(zag-zig)

插入

先按BST插入结点，再对此结点进行伸展。

查找(存在性/极值)

同BST查找，再对此结点进行伸展。

修改

同BST修改，再对此结点进行伸展。

删除(给定值/极值)

先伸展此结点，此时结点位于根，直接去掉根，现有两个子树。
对左子树进行“查找最大值”的操作，此时最大值将位于根，且没有右子树，将原来的右子树接上即可。

分离

在需要分离的地方插入一个节点，将其旋至根再删除，左右两个子树就是分离出来的两个treap.

合并

与分离互为逆运算，需满足其中一个treap的值都小于另外一个treap的结点的值。
添加一个根，将两棵树作为左右子树，再删除根即可。

prufer编码

详见 >> http://codeplay0314.gitcafe.io/2015/06/22/BZOJ1005/
有讲解同时也是经典题。

zkw线段树

在此Orz zkw神犇。
一种线段树的非递归实现方法，易理解且实现简单。
看心情写或不写代码。

可并堆

概述

堆都是可并的啊…为什么要叫可并堆呢…这跟“我忍俊不禁地笑了”是一种姿势吧er…真实的名字大概是“优并堆”（雾
一般的堆合并操作是O(n)O(n)的，而可并堆可以做到O(logn)O(logn)，比较简单易懂的是左偏树，由斜堆进化而来，插/删/合并都是O(logn)O(logn)，查询最小为O(1)O(1)；以后心情好再看斐波那契堆，除了删除结点，其他所有操作都可优化到O(1)O(1).
左偏树结构跟普通堆并没有太大区别，插入结点可看做一个结点的树和原树merge,这样保证了左偏的性质。

例题

模板题1 [ZOJ 2334] Monkey King

模板题2 [BZOJ 1455] 罗马游戏

Link Cut Tree

虚树

替罪羊树

树套树

朱刘算法

可持久化线段树

可持久化字典树

附录 - 参考资料

《分治算法在树的路径问题中的应用》 —— IOI2009 中国国家集训队论文 长沙市雅礼中学 漆子超
《统计的力量》 —— 清华大学 张琨玮
《算法竞赛入门经典 训练指南》 —— 刘汝佳