树基础

发表于 | 分类于 |

树的遍历:

  1. 中序、先序、后序
  2. bfs序

树的重心:

  1. 给定无根树，设以节点u为root时，其最大子树大小最小，则称u为该树的重心
  2. 若u为重心，则u的最大子树大小一定不超过n/2(n为总节点数)，同时，若u的最大子树大小不超过n/2，则u为该树的重心(易直观想到)
  3. 同一颗树最多存在两个重心(一颗子树为n/2,一颗子树为n/2-1，可知n一定为偶数，且两个重心一定相邻)（若节点数为偶数，总能找到种划分方法找到两个重心?—不一定)
  4. 向树中添加节点时，若节点数为偶数，则原本的两个重心有一个不为重心，若节点数为奇数，则可能出现新的重心，原本的重心仍为重心
  5. 两树通过一条边连接时，取较大的树的连接节点，则新的重心一定在该连接节点到该树的原本重心的路径上(若两树大小相同，则两个连接节点即为新重心)
  6. 树的重心到各个节点的距离之和最小

如何寻找重心?统计子树大小，若最大子树大小<=n/2，则为重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void dfs1(ll u,ll fa)
{
    ll mx = -1;
    size[u]=1;
    for(auto e:g[u])
    {
        if(e!=fa)
        {
            dfs1(e, u);
            mx = max(mx, size[e]);
            size[u] += size[e];
        }
        
    }
    mx = max(mx, sum - size[u]);
    if(mx<=sum/2) ans.push_back(u);
}

树的直径:

树的任意两个节点之间的最长距离即为树的直径

直径性质:

  1. 不存在负边权时，若存在多条相交直径，则直径的交点一定为中点(否则取两条直径的较长部分能拼出更长的路径)

如何求？

  1. 两次dfs，第一次以任意节点作为root，找到距离root最远的叶子节点，以该节点为根，再次dfs寻找距离该点最远的叶子节点，则此次两个节点之间的距离即为直径(若存在负边权则不成立)
  2. 树形dp，将随意一个节点作为root，记录每个节点向其子树衍生的最大深度和次大深度，取其和最大值即为直径(若要求记录直径经过节点，可在dp时记录对应节点)(存在负边权也成立)

树的LCA(最近公共祖先)

性质：

  1. 两点的LCA在其最短路径上
  2. 给定点集S，则该点集的LCA(S)=LCA(LCA(A),LCA(B)),其中A、B并集为S
  3. S必定在LCA(S)的子树内(包括根节点)

如何求?

  1. 倍增算法，给定两点，首先使其中一点向上爬，直至深度相同，判断两节点是否相同，若相同则为LCA；若不相同，两节点一起向上爬，每爬一步都判断是否相同(在树退化为链时复杂度退化为O(n))，故采用倍增算法对其优化(向上爬时采用二进制，即使树退化成链单次询问复杂度也有O(logN)，预处理复杂度为O(NlogN))

  2. tarjan算法(深度优先搜索树+并查集操作)，离线查询，将询问存在邻接表中(注意要存双向边)，大致思路就是利用了tarjan中的回溯思想，当遍历完所有子节点后，设置其并查集指向上一节点，通过一层层向上指寻找LCA(预处理复杂度为O(N)，询问复杂度为O(N+M))

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    vector<int>g[200005];
    vector<pair<int,int>>query;//first存点，second存ans编号
    int ans[200005];
    bool vis[200005];
    int p[200005];//并查集
    int n;//点数
    void init()
    {
        for(int i=1;i<=n;i++)
        {
            query[i].clear();
            g[i].clear();
            vis[i]=0;
            p[i]=i;
        }
    }
    void find(int x)
    {
        while(p[x]!=x)
        {
            x=p[x];
        }
        return x;
    }
    void union(int x,int y)
    {
        x=find(x);
        y=find(y);
        if(x!=y)
        {
            p[y]=x;//注意y指向x
        }
    }
    void tarjan(int x)
    {
        p[x]=x;
        vis[x]=1;
        for(auto e:g[x])
        {
            if(!vis[e])
            {
                tarjan(e);
                union(x,e);
            }
        }
        for(auto e:query[x])
        {
            if(vis[e.first])//另一个节点已被遍历到
            {
                ans[e.second]=find(e.first);
            }
        }
    }

  3. 欧拉序+RMQ问题(欧拉序，即进入节点时记录该点，对每个子节点dfs完，回溯时都再次记录该点,即模拟搜索路径),易知LCA是两个节点路径上的深度最小点，通过O(N)时间的预处理将问题转化为RMQ问题，然后用线段树、分块、ST表等方法维护区间最小值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int dfn[400025],depth[400025]，pos[200005];
    int tot=0;
    vector<int>g[200005];
    void dfs(int x,int dep)
    {
        dfn[++tot]=x;
        depth[tot]=dep;
        pos[x]=tot;
        for(auto e:g[x])
        {
            dfs(e,dep+1);
            dfn[++tot]=x;
            depth[tot]=dep;
    	}
    }

  4. 树链剖分，类似暴力法，不过目标是使两个节点跳到同一条重链上，此时重链上深度较小点即为LCA，每次让深度较大点跳向其重链头的父节点，预处理复杂度为O(N)，单次查询复杂度为O(logN)

  5. LCT(Link/Cut Tree)学了再补orz

本文内容大部分参考来源:

https://oi-wiki.org/graph/lca/#_7