算法学习记录：有关树的基础

前言：

  算法学习记录不是算法介绍，本文记录的是从零开始的学习过程（见到的例题，代码的理解……），所有内容按学习顺序更新，而且不保证正确，如有错误，请帮助指出。

学习工具：蓝桥OJ，LeetCode

本文归纳到目前为止见到的树。只需关注各个题目中有关树的部分即可。

目录

前言：

正文：

例题集：

1.蓝桥OJ 8617：LCA树上倍增

2.模型题：树型DP

---

正文：

对于一般的树：

数据量小时，用二维数组存储。

数据量大时，链式前向星（数组模拟链表）

重点记录一下链式前向星这种方法：

建立树：

#include <bits/stdc++.h>
using namespace std;
#define maxn 110000
int n, val[maxn];
struct Edge
{int nex, to;
}edge[maxn << 1];
int head[maxn], cnt;
int f[maxn][2];
void add(int from, int to)
{edge[++cnt].nex = head[from];//当前这条从from出发的边上一条边的编号head[from] = cnt;  //从from出发的最新的一条边的编号edge[cnt].to = to;   //当前边是到to去的return ;
}int main()
{for (int i = 1; i < n; ++ i ){int u, v;scanf("%d%d", &u, &v);add(u, v), add(v, u);  //双向边}return 0;
}

结构体edge用来存边：

里边的元素：nex和to

分别表示：同节点下上一条边的编号、这条边指向的结点编号。

head数组可以理解为构建链表时用的头节点，帮助构建链表并作为该链表的入口

遍历树：

void dfs(int u, int fa)
{for (int i = head[u]; i; i = edge[i].nex){int v = edge[i].to;if (v == fa)continue;dfs(v, u);f[u][0] += max(f[v][0], f[v][1]);f[u][1] += f[v][0];}return ;
}//dfs(1,0);

 i始终表示编号，第一次进入循环，i被赋值为该节点所连出的最后一条边的编号

v被赋值为这条边指向的结点编号

（因为是双向边）判断是否下一个结点是父节点，是的话跳过本次循环

下一次循环时，i被赋值edge[i].nex即这条边的上一条边的编号，

直到该编号为0，i=0循环结束

总结一下：

这种方法类似链表，每个结点、每条边都有编号，

类似链表的这种结构建立在每个结点下：

即该结点的每条边按照从后往前的顺序被连接形成“单链表”

这样做是为了遍历，并且能够存较大数据。

例题集：

1.蓝桥OJ 8617：LCA树上倍增

#include <bits/stdc++.h>using LL = long long;
using Pair = std::pair<int, int>;
#define inf 1'000'000'000'void solve(const int &Case) {int n;std::cin >> n;std::vector<std::vector<int>> G(n + 1);for (int i = 1; i < n; i++) {int u, v;std::cin >> u >> v;G[u].push_back(v), G[v].push_back(u);}std::vector<std::array<int, 21>> F(n + 1);std::vector<int> dep(n + 1);std::function<void(int, int)> dfs = [&](int x, int fax) {F[x][0] = fax;for (int i = 1; i <= 20; i++)F[x][i] = F[F[x][i - 1]][i - 1];for (const auto &tox: G[x]) {if (tox == fax)continue;dep[tox] = dep[x] + 1;dfs(tox, x);}};dfs(1, 0);auto glca = [&](int x, int y) {if (dep[x] < dep[y])std::swap(x, y);int d = dep[x] - dep[y];for (int i = 20; i >= 0; i--)if (d >> i & 1)x = F[x][i];if (x == y)return x;for (int i = 20; i >= 0; i--) {if (F[x][i] != F[y][i]) {x = F[x][i];y = F[y][i];}}return F[x][0];};int q;std::cin >> q;while (q--) {int x, y;std::cin >> x >> y;std::cout << glca(x, y) << '\n';}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T = 1;for (int Case = 1; Case <= T; Case++)solve(Case);return 0;
}

这题中使用二维数组存储了树，遍历数组G 就是在遍历树上的每一个结点

对于每一个结点，数组里存着它的父节点和子节点对应编号。

dfs函数的两个参数分别是：子节点编号和父节点编号

dep数组用来存放深度

2.模型题：树型DP

#include <bits/stdc++.h>
using namespace std;
#define maxn 110000
int n, val[maxn];
struct Edge
{int nex, to;
}edge[maxn << 1];
int head[maxn], cnt;
int f[maxn][2];
void add(int from, int to)
{edge[++cnt].nex = head[from];//当前这条从from出发的边上一条边的编号head[from] = cnt;  //从from出发的最新的一条边的编号edge[cnt].to = to;   //当前边是到to去的return ;
}
void dfs(int u, int fa)
{for (int i = head[u]; i; i = edge[i].nex){int v = edge[i].to;if (v == fa)continue;dfs(v, u);f[u][0] += max(f[v][0], f[v][1]);f[u][1] += f[v][0];}return ;
}
int main()
{scanf("%d", &n);for (int i = 1; i <= n; ++ i )scanf("%d", &val[i]), f[i][1] = val[i];for (int i = 1; i < n; ++ i ){int u, v;scanf("%d%d", &u, &v);add(u, v), add(v, u);}dfs(1, 0);printf("%d\n", max(f[1][0], f[1][1]));return 0;
}

 DP的题目就是在遍历树时加一个dp 数组，伴随遍历过程完成动态规划的数组更新。