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)已经连通，则加入后会形成环。不能选择。试图将(u,v)加入树中。

4.最小瓶颈生成树

使生成树最大边权最小

最小生成树符合最小瓶颈生成树条件

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],cnt,top[N],pa[N];

void dfs1(int x,int fa){
    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){
    dfn[x]=++cnt;
    if(son[x]!=0){
        top[son[x]]=top[x];
        dfs2(son[x],x);
    }
    for(auto y:G[x])if(y!=pa[x]&&y!=son[x]){
        top[y]=y;
        dfs2(y,x);
    }
}

int main(){
    dfs1(1,0);
    top[1]=1;
    dfs2(1,0);
}

4.查询路径最值

把路径分成几条重链（单点也是特殊重链）

求路径上的每条重链的最值，然后在这些最值中求出最后的最值。

求重链最值可以在DFS序上用线段树或ST表。