树

2021 年 5 月 9 日 星期日(已编辑)
1
这篇文章上次修改于 2021 年 5 月 9 日 星期日，可能部分内容已经不适用，如有疑问可询问作者。

树

树

存储

邻接表

  • 对于无根树：为每个结点开辟一个线性列表，记录所有与之相连的结点。

    std::vector<int> adj[N];

  • 对于有根树：

    • 方法一：若给定的是无向图，则仍可以上述形式存储。下文将介绍如何区分结点的上下关系。

    • 方法二：若输入数据能够确保结点的上下关系，则可以利用这个信息。为每个结点开辟一个线性列表，记录其所有子结点；若有需要，还可在另一个数组中记录其父结点。

      std::vector<int> children[N];
int parent[N];

遍历

DFS

  • 先序遍历：左中右

    void preTrav(BiTree* root) 
{
    if (root) 
    {
        cout << root->key << " ";
        preTrav(root->left);
        preTrav(root->right);
    }
}

树的直径

两次 DFS

第一次从任意节点开始 DFS 找到最远的节点 z，第二次从 z 开始 DFS 找到最远的节点 z'，则 dis(z, z') 为树的直径

  • 定理：在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。
  • 不适用于存在负权边的树
const int N = 10000 + 10;

int n, c, d[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}

树形 DP

我们记录当 11 为树的根时，每个节点作为子树的根向下，所能延伸的最远距离 d1d_1，和次远距离 d2d_2，那么直径就是所有 d1+d2d_1+d_2 的最大值。

树形 DP 可以在存在负权边的情况下求解出树的直径。

const int N = 10000 + 10;

int n, d = 0;
int d1[N], d2[N];
vector<int> E[N];

void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[u]);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}

LCA

树上两个节点的最近公共祖先

性质

  • LCA(u) = u
  • 若 LCA(u, v) = u 则 u 是 v 的祖先
  • 如果 u 不为 v 的祖先并且 v 不为 u 的祖先，那么 u, v 分别处于 LCA(u, v) 的两棵不同子树中
  • 前序遍历中，LCA(S) 出现在所有 S 中元素之前，后序遍历中 LCA(S) 则出现在所有 S 中元素之后
  • 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 LCA(A∪B)=LCA(LCA(A),LCA(b))LCA(A\cup B)=LCA(LCA(A),LCA(b))
  • 两点的最近公共祖先必定处在树上两点间的最短路上
  • d(u,v)=h(u)+h(v)−2h(LCA(u,v))d(u, v) = h(u) + h(v) -2h(LCA(u,v))，其中 d 是树上两点间的距离，h 代表某点到树根的距离

在线 · 倍增

倍增算法是最经典的 LCA 求法，他是朴素算法的改进算法。通过预处理 fax,ifa_{x,i} 数组，游标可以快速移动，大幅减少了游标跳转次数。 fax,ifa_{x,i} 表示点 xx 的第 2i2^i 个祖先。 数组可以通过 DFS 预处理出来。

现在我们看看如何优化这些跳转： 在调整游标的第一阶段中，我们要将 u,vu, v 两点跳转到同一深度。我们可以计算出 u,vu, v 两点的深度之差，设其为 yy。通过将 yy 进行二进制拆分，我们将 yy 次游标跳转优化为 的二进制表示所含 1 的个数 次游标跳转。 在第二阶段中，我们从最大的 ii 开始循环尝试，一直尝试到 00 （包括 00），如果 fau,i≠fav,ifa_{u,i}\neq fa_{v,i}，则 u←fau,i,v←fav,iu\leftarrow fa_{u,i}, v\leftarrow fa_{v,i}，那么最后的 LCA 为 fau,0fa_{u,0}。

倍增算法的预处理时间复杂度为 O(nlog⁡n)O(n\log n)，单次查询时间复杂度为 O(log⁡n)O(\log n) 。 另外倍增算法可以通过交换 fa 数组的两维使较小维放在前面。这样可以减少 cache miss 次数，提高程序效率。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define MXN 50007
using namespace std;
std::vector<int> v[MXN];
std::vector<int> w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
  // 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
  // 2^(i-1) 的祖先节点。
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  // 遍历子节点来进行 dfs。
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}

// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
  // 令 y 比 x 深。
  if (dep[x] > dep[y]) swap(x, y);
  // 令 y 和 x 在一个深度。
  int tmp = dep[y] - dep[x], ans = 0;
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
  // 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
  if (y == x) return ans;
  // 不然的话，找到第一个不是它们祖先的两个点。
  for (int j = 30; j >= 0 && y != x; --j) {
    if (fa[x][j] != fa[y][j]) {
      ans += cost[x][j] + cost[y][j];
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  // 返回结果。
  ans += cost[x][0] + cost[y][0];
  return ans;
}

int main() {
  // 初始化表示祖先的数组 fa，代价 cost 和深度 dep。
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // 读入树：节点数一共有 n 个。
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    scanf("%d %d %d", &a, &b, &c);
    ++a, ++b;
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  // 为了计算 lca 而使用 dfs。
  dfs(1, 0);
  // 查询 m 次，每一次查找两个节点的 lca 点。
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &a, &b);
    ++a, ++b;
    printf("%d\n", lca(a, b));
  }
  return 0;
}

离线 · Tarjan

Tarjan 算法 是一种 离线算法，需要使用 并查集 记录某个结点的祖先结点。做法如下：

  1. 首先接受输入（邻接链表）、查询（存储在另一个邻接链表内）。查询边其实是虚拟加上去的边，为了方便，每次输入查询边的时候，将这个边及其反向边都加入到 queryEdge 数组里。
  2. 然后对其进行一次 DFS 遍历，同时使用 visited 数组进行记录某个结点是否被访问过、parent记录当前结点的父亲结点。
  3. 其中涉及到了 回溯思想，我们每次遍历到某个结点的时候，认为这个结点的根结点就是它本身。让以这个结点为根节点的 DFS 全部遍历完毕了以后，再将 这个结点的根节点 设置为 这个结点的父一级结点。
  4. 回溯的时候，如果以该节点为起点，queryEdge 查询边的另一个结点也恰好访问过了，则直接更新查询边的 LCA 结果。
  5. 最后输出结果。

Tarjan 算法需要初始化并查集，所以预处理的时间复杂度为 O(n)O(n)，Tarjan 算法处理所有 mm 次询问的时间复杂度为 O(n+m)O(n+m)。但是 Tarjan 算法的常数比倍增算法大。

#include <algorithm>
#include <iostream>
using namespace std;

class Edge {
 public:
  int toVertex, fromVertex;
  int next;
  int LCA;
  Edge() : toVertex(-1), fromVertex(-1), next(-1), LCA(-1){};
  Edge(int u, int v, int n) : fromVertex(u), toVertex(v), next(n), LCA(-1){};
};

const int MAX = 100;
int head[MAX], queryHead[MAX];
Edge edge[MAX], queryEdge[MAX];
int parent[MAX], visited[MAX];
int vertexCount, edgeCount, queryCount;

void init() {
  for (int i = 0; i <= vertexCount; i++) {
    parent[i] = i;
  }
}

int find(int x) {
  if (parent[x] == x) {
    return x;
  } else {
    return find(parent[x]);
  }
}

void tarjan(int u) {
  parent[u] = u;
  visited[u] = 1;

  for (int i = head[u]; i != -1; i = edge[i].next) {
    Edge& e = edge[i];
    if (!visited[e.toVertex]) {
      tarjan(e.toVertex);
      parent[e.toVertex] = u;
    }
  }

  for (int i = queryHead[u]; i != -1; i = queryEdge[i].next) {
    Edge& e = queryEdge[i];
    if (visited[e.toVertex]) {
      queryEdge[i ^ 1].LCA = e.LCA = find(e.toVertex);
    }
  }
}

int main() {
  memset(head, 0xff, sizeof(head));
  memset(queryHead, 0xff, sizeof(queryHead));

  cin >> vertexCount >> edgeCount >> queryCount;
  int count = 0;
  for (int i = 0; i < edgeCount; i++) {
    int start = 0, end = 0;
    cin >> start >> end;

    edge[count] = Edge(start, end, head[start]);
    head[start] = count;
    count++;

    edge[count] = Edge(end, start, head[end]);
    head[end] = count;
    count++;
  }

  count = 0;
  for (int i = 0; i < queryCount; i++) {
    int start = 0, end = 0;
    cin >> start >> end;

    queryEdge[count] = Edge(start, end, queryHead[start]);
    queryHead[start] = count;
    count++;

    queryEdge[count] = Edge(end, start, queryHead[end]);
    queryHead[end] = count;
    count++;
  }

  init();
  tarjan(1);

  for (int i = 0; i < queryCount; i++) {
    Edge& e = queryEdge[i * 2];
    cout << "(" << e.fromVertex << "," << e.toVertex << ") " << e.LCA << endl;
  }

  return 0;
}

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...