导航网站建站系统,建设部网站公示,青岛seo服务,wordpress面包屑导航代码前言#xff1a; 算法学习记录不是算法介绍#xff0c;本文记录的是从零开始的学习过程#xff08;见到的例题#xff0c;代码的理解……#xff09;#xff0c;所有内容按学习顺序更新#xff0c;而且不保证正确#xff0c;如有错误#xff0c;请帮助指出。
学习工具…前言 算法学习记录不是算法介绍本文记录的是从零开始的学习过程见到的例题代码的理解……所有内容按学习顺序更新而且不保证正确如有错误请帮助指出。
学习工具蓝桥OJLeetCode
本文归纳到目前为止见到的树。只需关注各个题目中有关树的部分即可。
目录
前言
正文
例题集
1.蓝桥OJ 8617LCA树上倍增
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即这条边的上一条边的编号
直到该编号为0i0循环结束 总结一下
这种方法类似链表每个结点、每条边都有编号
类似链表的这种结构建立在每个结点下
即该结点的每条边按照从后往前的顺序被连接形成“单链表”
这样做是为了遍历并且能够存较大数据。
例题集
1.蓝桥OJ 8617LCA树上倍增
#include bits/stdc.husing LL long long;
using Pair std::pairint, int;
#define inf 1000000000void solve(const int Case) {int n;std::cin n;std::vectorstd::vectorint 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::vectorstd::arrayint, 21 F(n 1);std::vectorint dep(n 1);std::functionvoid(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 数组伴随遍历过程完成动态规划的数组更新。
