Htto的小站
0%

树上算法

发表于 更新于 分类于 ，

基本概念

树是一种特殊的图，它没有环，也没有横叉边，树一般都有一个节点作为根(root),当然也有没有根节点的无根树。二叉树是比较常见的一种树建树比较规律，对于不定叉树我们建树就要借助建图的方法。

树最常用的一个性质\(m=n-1\),即边数等于节点数减一。

树上dfs

我们用图来表示树，图中是不能包含根节点以及节点之间父子关系的，我们就要需要通过dfs从根节点搜索来确定这种关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int par[maxn];
int depth[maxn];
void dfs(int u, int p)
{
    for (auto edge_no : G[u])
    {
        int to = edges[edge_no].to;
        // 防止子节点向父节点方向搜索
        if (to == p)
            continue;
        // 记录一下父子关系
        par[to] = u;
        depth[to]=depth[u]+1;
        dfs(to, u);
    }
}

最近公共祖先

给定一棵树，让你快速求两个节点的最近公共祖先。

解题思路

  1. 用图的方法建树，然后算出每个节点的深度以及父节点par[u];
  2. 计算\(LCA(u,v)\),首先需要将\(u,v\)提升到同一高度。首先比较u,v深度，深度较大节点的需要起跳到深度较小节点的高度。
  3. u,v到达同一高度后一起跳，直到u,v相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int LCA(int u, int v)
{
    // LCA(u,v)=LCA(v,u) 所以参数可以互换。
    // 交换了以后就不需要分情况讨论了，保证了u的深度大于v
    if (depth[u] < depth[v])
        swap(u, v);
    // u的深度比v大，我们就不停的让u往上跳
    while (depth[u] > depth[v])
        u = par[u];
    // 保证深度一样后，我们就可以一起起跳，最终一定会在同一高度相遇
    while (u != v)
    {
        u = par[u];
        v = par[v];
    }
    return u;
}

如果这颗树是一条链，而且u,v一个一头一尾，那么时间复杂度就是\(O(N)\)了。这题会TLE两个点。那么我们该如何优化呢。

优化

使用倍增来优化我们可以获得\(O(\log n)\)的时间复杂度。我们的par数组可以记录\(2^k\)级祖先，比如\(par[u][0]\)代表u的父节点，\(par[u][1]\)是父亲节点的父亲节点(往上数第二个)，\(par[u][k]\)就是往上数第\(2^k\)个节点。

对于第二步，u和v的深度之差一定是一个具体的值，这个值可以看作一个二进制。我们拆分这个二进制。

1
2
3
4
int dif = depth[u] - depth[v];
for (int i = LOG; i >= 0; i--)
        if (have_bit(dif, i))
            u = par[u][i];

对于第三步，假设我们最近公共祖先深度为\(d\)，我们不知道该跳多高，那么我们可以从大往小尝试起跳（有点类似于二分在里面）

1
2
3
4
5
6
7
8
for (int i = LOG - 1; i >= 0; i--)
{
    if (par[u][i] != par[v][i])
    {
        u = par[u][i];
        v = par[v][i];
    }
}

最后优化后的LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int LCA(int u, int v)
{
    if (depth[u] < depth[v])
        swap(u, v);
    int dif = depth[u] - depth[v];
    for (int i = LOG; i >= 0; i--)
        if (have_bit(dif, i))
            u = par[u][i];
    
    if (u == v)
        return u;
    for (int i = LOG - 1; i >= 0; i--)
    {
        if (par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

在使用LCA之前我们需要初始化一下par数组，\(par[u][0]\)已经在dfs中算出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
void init()
{
    memset(par, 0, sizeof(par));

    dfs(s, 0);
    for (int i = 1; i < LOG; i++)
    {
        for (int k = 1; k <= n; k++)
        {
            par[k][i] = par[par[k][i - 1]][i - 1];
        }
    }
}

树的重心

树的重心：即树上所有节点到某点距离之和最小的点。树的重心有许多有用的性质

性质1

某个点是树的重心等价于它最大子树大小不大于整棵树大小的一半

性质2

树至多有两个重心。如果树有两个重心，那么它们相邻。此时树一定有偶数个节点，且可以被划分为两个大小相等的分支，每个分支各自包含一个重心。

计算重心

我们可以一趟dfs，记录每个节点的所有子树节点数之和以及最大子树大小，最大子树可以是沿dfs上父节点延伸的子树，我们用n-W[u]来计算其大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int W[maxn];
// max son weight
int Msw[maxn];
void dfs(int u, int p)
{
    W[u] = 1;
    for (auto edge_no : G[u])
    {
        int to = edges[edge_no].to;
        if (to == p)
            continue;
        dfs(to,u);
        W[u]+=W[to];
        Msw[u]=max(Msw[u],W[to]);
    }
    Msw[u]=max(Msw[u],n-W[u]);
}

找重心

1
2
3
4
5
dfs(1, 0);
int t = 1;    
for (int i = 2; i <= n; i++)
    if (Msw[i] < Msw[t])
        t = i;

找出Masw最小的节点就好啦，注意重心可能有两个，这两个个重心Msw一定相等。当然如果\(Msw <= n/2\) 也一定是重心。

参考

完整代码

  • LCA 

    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
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    using namespace std;
    const int maxn = 5e5 + 5;
    const int LOG = 25;
    int n, m, s;
    struct Edge
    {
        int from, to;
    };
    vector<int> G[maxn];
    vector<Edge> edges;
    void add_edge(int u, int v)
    {
        edges.push_back({u, v});
        G[u].push_back(edges.size() - 1);
    }
    void input()
    {
        cin >> n >> m >> s;
        for (int i = 1; i < n; i++)
        {
            int a, b;
            cin >> a >> b;
            add_edge(a, b);
            add_edge(b, a);
        }
    }
    int par[maxn][LOG];
    int depth[maxn];
    void dfs(int u, int p)
    {
        for (auto edge_no : G[u])
        {
            int to = edges[edge_no].to;
            // 防止子节点向父节点方向搜索
            if (to == p)
                continue;
            // 记录一下父子关系
            par[to][0] = u;
            depth[to] = depth[u] + 1;
            dfs(to, u);
        }
    }
    void init()
    {
        memset(par, 0, sizeof(par));

        dfs(s, 0);
        for (int i = 1; i < LOG; i++)
        {
            for (int k = 1; k <= n; k++)
            {
                par[k][i] = par[par[k][i - 1]][i - 1];
            }
        }
    }
    bool have_bit(int x, int i)
    {
        return (x >> i) & 1;
    }
    int LCA(int u, int v)
    {
        if (depth[u] < depth[v])
            swap(u, v);
        for (int i = LOG; i >= 0; i--)
        {
            if (have_bit(depth[u] - depth[v], i))
            {
                u = par[u][i];
            }
        }
        if (u == v)
            return u;
        for (int i = LOG - 1; i >= 0; i--)
        {
            if (par[u][i] != par[v][i])
            {
                u = par[u][i];
                v = par[v][i];
            }
        }
        return par[u][0];
    }
    int main()
    {
        input();
        init();
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            cin >> x >> y;
            cout << LCA(x, y) << endl;
        }
        return 0;
    }

  • 重心 

    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
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const int maxn = 1e5 + 5;
    struct Edge
    {
        int from, to;
    };
    vector<int> G[maxn];
    vector<Edge> edges;
    int n, m;
    int W[maxn];
    // max son weight
    int Msw[maxn];
    int depth[maxn];
    void add_edge(int u, int v)
    {
        edges.push_back({u, v});
        G[u].push_back(edges.size() - 1);
    }
    void input()
    {
        cin >> n;
        for (int i = 1; i < n; i++)
        {
            int u, v;
            cin >> u >> v;
            add_edge(u, v);
            add_edge(v, u);
        }
    }
    void dfs(int u, int p)
    {
        W[u] = 1;
        for (auto e_no : G[u])
        {
            int to = edges[e_no].to;
            if (to == p)
                continue;
            dfs(to, u);
            W[u] += W[to];
            Msw[u] = max(Msw[u], W[to]);
        }
        Msw[u] = max(Msw[u], n - W[u]);
    }
    void dfs2(int u, int p)
    {
        for (auto e_no : G[u])
        {
            int to = edges[e_no].to;
            if (to == p)
                continue;
            depth[to] = depth[u] + 1;
            dfs2(to, u);
        }
    }
    int main()
    {
        input();
        dfs(1, 0);
        int g = 1;
        for (int i = 2; i <= n; i++)
        {
            if (Msw[i] < Msw[g])
                g = i;
        }
        dfs2(g, 0);
        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
            sum += depth[i];
        }
        cout << g << " " << sum;
        return 0;
    }

^ 重心的性质引用了Pecco的笔记，具体证明见Pecco-树的重心