今日主要学习树论。
一.最近公共祖先（LCA）
最近公共祖先的求解主要分为几个部分：
1.初始化：加边，初始化每个节点的祖先节点，初始化每个节点的深度。
加边：使用vector存储，注意一共输入n−1n-1n−1跳条双向边。
初始化每个祖先节点：
f[x][0]表示节点xxx的父亲。
f[x][1]表示节点xxx的祖父（父亲的父亲）。
f[x][2]表示节点xxx的超级祖父（祖父的祖父）。
由此可知：f[x][i]=f[f[x][i−1]][i−1]f[x][i]=f[f[x][i-1]][i-1]f[x][i]=f[f[x][i−1]][i−1]
初始化每个节点的深度：每个节点的深度=每个节点的父节点深度+1
2.求最近公共最先：将两个点提升至同一高度，找寻它们的公共祖先。
将两个点提升至同一高度：一层一层的提升会超时间复杂度，选择倍增的思想。
寻找它们的公共祖先：从后往前找，使用排除的思想。
模版：链接描述
代码：
二.树上路径最小值
其实和上一题差不多。
但是需要求最小点权，所以需要多加一个mi[][]mi[][]mi[][]数组。
mi[][]mi[][]mi[][]和上一道题目中的f[][]f[][]f[][]差不多。
它表示的是节点xxx到xxx的父/祖父/超级祖父节点的最小点权。
这是mi[][]mi[][]mi[][]的计算公式：mi[i][j]=min(mi[i][j−1],mi[f[i][j−1]][j−1]);mi[i][j]=min(mi[i][j-1],mi[f[i][j-1]][j-1]);mi[i][j]=min(mi[i][j−1],mi[f[i][j−1]][j−1]);
代码：
三.树上差分
这是一个比较古怪的题目，要考虑如何在树上做差分的同时，也代表要在树上做前缀和。
题目：链接描述
大概是这样子的：
（两个）
