2020.2.2
树形问题
1.基础知识
1.基本性质
有n 个点，n − 1 条边的连通无向的无环图是无根树
规定无根树某节点为根节点，就变成有根树
树上两点间有且仅有一条路径，该路径的长度称为两点的距离
除根节点外，每个节点有且只有一个父亲
除了叶节点，每个节点有至少一个儿子
2.规定
fa~i~：点 i 的父亲
d~i~：点 i 的深度（除非说明，根节点深度为 0）
size~i~：点 i 子树的大小
dist~i,j~：点 i 和点 j 的距离
3.树的直径
定义：一棵带权树中最远的两个节点之间的路径(距离)。
推论：直径的端点一定是叶子
反证：如果一个端点不是叶子，那么它的儿子到另一个端点距离一定比原直径长，与定义不符。所以直径端点一定是叶子
推论：对树中的一个点x，离x最远的点一定是直径的一个端点。
证明：以x为根DFS或BFS，求出每个点到x的距离，并得到离x最远的点u。再求出每个点到u的距离，并得到离u最远的点v，那么这里的(u,v)就是最长的路径（因为v离u最远，所以如果还有更长的，端点一定不是u或v，但是u离x最远，所以更长的路径不存在，(u,v)最长）路径 (u, v) 即为树的直径
2.倍增求LCA
1.祖先：x到根的路径上除x之外的所有点
2.LCA(最近公共祖先)
两个节点的辈分最小（深度最大）的祖先。
LCA的应用：快速查询两点距离：
两点距离就是两点深度和减去两倍的LCA的深度
要想求出LCA，暴力的算法就是先将深度较大的往上走，直到两节点深度相同，接着同时往上走，直到两点重合，就找到了LCA(当前重合位置的节点)
时间复杂度：O(n)
3.倍增
可以用二进制优化，先预处理出每个节点的2^i^代祖先，然后把之前将节点一步一步往上走的操作，优化成一次2^i^步的操作，时间复杂度优化为O(log~2~n)（易证，i要从大到小，就像乌鸦喝水先放大石子一样）
代码：
int LCA (int x, int y) {//求x,y的LCA
if (d[x] < d[y])
swap(x, y);//保证x深度大
int k = d[x] - d[y];//深度差
for (int j = 16; j >= 0; j--)
if (k & (1 << j))//如果x往上跳不会跳过头
x = f[x][j];//往上跳2^j步
if (x == y)//恰好重合
return x;//当前重合的位置就是LCA
for (int j = 16; j >= 0; j--)//两点一起跳
if (f[x][j] != f[y][j])//没有过头（直到都到了LCA儿子的位置）
x = f[x][j], y = f[y][j];//一起跳2^j步
x = fa[x];//此时的父亲就是LCA
return x;
}
3.生成树
1.MST（最小生成树）
在有n个点m条边的无向带权图中，选出n-1条边形成一棵树，使生成树边权和最小
Kruskal算法：
将边按边权从小到大排序，并依次考虑每条边(u,v)。若u,v节点已经连通，则加入后会形成环，不能选择。如果能加入，就加入。（等到加入n-1条边为止）
4.最小瓶颈生成树
使生成树最大边权最小
易知Kruskal生成的最小生成树符合最小瓶颈生成树条件
4.DFS序和树链剖分
1.DFS序
对树DFS时记录点的序号所产生的序列。
推论：每个点的子树对应DFS序中的连续区间。
应用：将子树操作转化为区间操作
2.树链剖分（这里只讨论重链剖分）
把树上问题转化为DFS序列上的问题（点带权的树）
应用：解决（单点/子树/路径）（修改/询问(最值/总和)）问题，将树上的操作转化为序列操作
轻边的子树大小小于等于根节点父亲的子树的大小的二分之一
轻边条数数量级：O(logn)
重链条数数量级：O(logn)
首次DFS：求出节点子树大小，重儿子
再次DFS：先访问重儿子，再访问轻儿子，记录DFS序，这样就能使每条重链对应第二次DFS序上的一段区间，记录重链链顶（整条链深度最小的节点）。
老师的(伪)代码：
vector<int> G[N];
int siz[N]/*子树大小*/,son[N]/*重儿子*/,dfn[N]/*DFS序*/,cnt/*计数器*/,top[N]/*链顶*/,pa[N]/*父亲*/;
void dfs1(int x,int fa){//首次dfs
siz[x]=1;//子树包括它本身
pa[x]=fa;//记录父亲
for(auto y:G[x]){//累计子树大小
if(y!=fa)dfs1(y,x),siz[x]+=siz[y];
}
int mx=0;//转存儿子的最大子树
for(auto y:G[x])if(y!=fa){//避免把父亲当儿子
if(mx<siz[y]) {//找出重儿子
mx=siz[y];
son[x]=y;
}
}
}
void dfs2(int x){//第二次dfs
dfn[x]=++cnt;//记录重儿子有限的dfs序
if(son[x]!=0){//如果x有重儿子
top[son[x]]=top[x];//儿子链顶就是父亲所在重链链顶
dfs2(son[x],x);//继续搜
}
for(auto y:G[x])if(y!=pa[x]&&y!=son[x]){//然后在依次搜其他的儿子
top[y]=y;//由于新的一条重链，所以新链顶就是当前的y
dfs2(y,x);
}
}
int main(){
dfs1(1,0);//首次dfs
top[1]=1;//最开始链顶就是根
dfs2(1,0);//再次dfs
}