- 树的存储（邻接表）和深度优先遍历
//数组的邻接表存储
vector<int> q[maxn]; //这个是一般的
int fi[maxn]; //存储节点的儿子个数
int to[maxn]; //存储节点的具体每个儿子
int ne[maxn]; //指向该节点的下一个儿子
void link(int x,int y){ //这个函数一定要记住 一条由x指向y的边
to[++m]=y; //具体的儿子
ne[m]=fi[x]; //下一个（上一个儿子）倒着的
fi[x]=m; //儿子数量更新
}
//如果是vector<int> 的话，直接push_back就可以了
//树的深度优先遍历（有树根）
void dfs(int x){
viste(x); //do something
for(int i=fi[x];i;i=ne[i]) dfs(to[i]); //这个书写顺序也要记住
//....
}
//无根树
void dfs1(int x,int fa){
viste(x); //do something
for(int i=fi[x];i;i=ne[i]) if(to[i]!=fa) dfs(to[i],x); //要排除数组里面的父亲
//....
}
//例：求树中每棵子树的大小和每个节点的深度（基础，用子树的状态去更新根节点的状态，以及深度都是很有用的东西）
//每个点的子树大小等于它的所有儿子的子树大小之和+1，深度为父亲的深度+1
int size[maxn]; //树的大小
int de[maxn]; //树的深度
void getsi(int x,int fa){
si[x]=1;
de[x]=de[fa]+1;
for(int i=fi[x];i;i=ne[i]){
if(to[i]!=fa) {
dfs(to[i],x);
size[x]+=si[to[i]];
}
}
}
- 求两个节点的LCA，这里讲了四种算法
第一种、暴力
时间复杂度：与两点之间的距离有关，但是实现简单，随机产生的树期望高度是O(logN)的，所以可能能够使用，最大的优点是允许树动态改变
//LCA问题，最近公共祖先
//算法一、两个点逐渐向根移动（暴力）
//时间复杂度高，但是它允许树动态改变，只需要知道每个点的父亲和深度，（另一个可以处理动态情况的数据结构式动态树）
int getlac(int x,int y){
while(de[x]>=de[y]) x=fa[x]; //谁深度大，谁就往上移
else y=fa[y];
return x;
}
第二种、倍增法
//算法二、倍增法求LCA,让节点每次向上走2的幂次步
int anc[maxn][maxlog];
//step 1.求出倍增数组anc[maxn][maxlog] maxlog是最小的满足2^x>=maxdeep的x，anc[x][y]为节点i向上走2^j步能走到节点，j=0，anc[i][j]就是节点的父亲
//anc[i][j]=anc[anc[i][j-1]][j-1]
//step 2.把两个点移到同一深度，这个有两种方法，第一种是把de[y]-de[x]表示为2进制，i号位上面是1，就移动2^i次，第二种是从大到小扫描i，
//如果anc[x][j]的深度大于y，那么我们就跳x，i
//step 3.求出LCA,这个做法可以看成是通过二分法求解走最大L-1步的过程，直到完全不能走了为止，再让x,y各向上走一步，则为LCA
void dfs(int x,int fa){//求出倍增数组anc[maxn][maxlog]
de[x]=de[fa]+1;
anc[x][0]=fa;
for(int i=1;i<maxlog;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
for(int i=fi[x];i;i=ne[i]){
if(to[i]!=fa) dfs(to[i],x);
}
}
int getlac(int x,int y){
if(de[x]<de[y]) swap(x,y); //x在下面
for(int i=maxlog-1;i;i--){
if(de[anc[x][i]]>=de[y]) x=anc[x][i]; //走到同一深度
}
if(x==y) return x;
for(int i=maxlog-1;i;i--){
if(anc[x][i]!=anc[y][i]){
x=anc[x][i];
y=anc[y][i]; //都往上走
}
}
return anc[x][0]; //直到完全不能走了为止，再让x,y各向上走一步，则为LCA
}
第三种、转RMQ问题
转化为欧拉序列上的RMQ问题，采用ST算法
欧拉序列：每经过一次结点，都进行一次统计产生的DFS序列
RMQ：指一类查询连续区间的最大（小）值问题
ST算法：求解RMQ问题的快速方法
要有欧拉序列和深度序列，求LCA(x,y)时，在欧拉序列中的位置分别位pos[x],pos[y]，那么它们的LCA就是【pos[x],pos[y]】区间里面深度小的点
模板：https://blog.csdn.net/diogenes_/article/details/80794838 【模板】ST表求解RMQ问题 Sparse Table 算法给出一个 n个元素的数组 A1,A2,…,An，求解 min(l,r): 计算 min{Al,Al+1,…,ArAl}其实就是用了2分的思想，倍增法的思想，把求解转变成0(1）的问题
//令 d(i,j) 为从 i开始的， 长度为2^j 的一段元素中的最小值。根据倍增思想，d(i,j) 可以通过 d(i,j-1) 和 d(i+2^j-1,j-1)
//转移得到，具体操作就是对两个数取 min 。预处理的时间复杂度是 O(nlog2n) 。
//我们令k为满足 2^k<=R+L+1的最大整数。则可知 k=log2R+L+1.则以l开头,以R结尾的两个长度为2^k的区间合并起来就覆盖了[L,R] 。由于是求范围最小值，有元素被重复计算也没问题。
//则 Query(L,R)=min(d(L,k),d(R-2^k+1,k))Query(L,R)=min(d(L,k),d(R+2^k+1,k)) 。
void inti(int n){
for(int i=1;i<=n;i++) d[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r){
int k=log2(r-l-1);
return min(d[l][k],d[r-(1<<k)+1][k]);
}
第四种、Tarjan算法
//算法四、Tarjan算法
//离线算法，适合时间限制很严格，倍增法会超时的情况
//1、DFS整棵树，节点x是属于自身的集合（并查集）Sx
//2、DFS(X)时，每次访问玩子树y，把Sy合并到Sx
//x的所有子节点访问完，标记x已经访问
//遍历所有关于x的询问（x,y),如果y已经被访问，那么询问的答案为find(y)
int vis[maxn];
void dfs(int x){
for(int i=0;i<q[x].size();i++){
dfs(q[x][i]);
onion(q[x][i],x);
}
vis[x]=1;
for(int i=0;i<query[x].size();i++){
int y=query[x][i];
if(vis[y]) ans[x][y]=find(y);
}
}
//例：求树上两个点之间的距离
//求出两个点的LCA,距离等于de[x]+de[y]-2de[LCA]
一个例子、括号与树的相互转化
//括号序列与树的相互转化，每一对括号看成是节点，直接套住的括号对看作是子节点，
int f[maxn],now;
char s[maxn*2];
void sovle(int fa){
while(s[now]!=')'){ //扫过嵌套的内容，直到遇到右括号
++now;
link(fa,++n);
sovle(n);
}
++now;
}
//对树的深度优先遍历序列输出树的括号序列
void dfs1(int x){
cout<<"(";
for(int i=fi[x];i;i=ne[i]) dfs(to[i]);
cout<<")";
}
- 树的直径、中心、重心
直径：两点间不重复经过的边和点道路成为两点间的路径，树的直径时树中两点间的最长路径
树的中心：该店到树中其他点的距离，最远距离最小（可能有多个）
树的重心：无根树，若某个节点的每个儿子的子树大小都小于等于n/2,则这个点叫做该数的重心
一、直径
//直径：两点间不重复经过的边和点道路成为两点间的路径，树的直径时树中两点间的最长路径
//求解1、两次遍历找出书的一条直径
//第一次。找出距离某个点最远的一个点x
//第二次。找出距离结点x最远的一个点y
//直径=x到y的简单路径
//应该是无根树
void getdu(int x,int fa){
de[x]=de[fa]+1;
for(int i=fi[x];i;i=ne[i]){
if(to[i]!=fa) dfs(to[i],x);
}
}
void wrok(){
getde(1,0); //根节点作为第一个节点
int x=1;
for(int i=2;i<=n;i++){
if(de[i]>de[x]) x=i; //找出深度最大的点
}
getdu(x,0); //深度最大的点x作为根节点，找出深度最大的点（改变de[]数组）
int y=1;
for(int i=2;i<=n;i++){
if(de[i]>de[y]) y=i;
}
cout<<x<<" "<<y<<" "<<de[y]<<endl; //x--y，深度
}
//求解2、LCA求解
//一条直径上的所有点都有一个共同的LCA,在DFS的过程中，我们考虑以他为LCA可能的直径，维护以每个点为顶端的最长链和次长链，然后用最长链加上次长链，维护直径
int len=0;
int dfs(int x,int fa){
int mx,mmx; //最长和次长
for(int i=fi[x];i;i=ne[i]){
if(to[i]!=fa) {
int temp=dfs(to[i],x);
if(temp>mx){
mmx=mx;
mx=temp;
}
else if(temp>mmx) mmx=temp;
}
}
len=max(len,mmx+mx);
return len;
}
//例子：
//1、给定一棵树，对于每一个点，求出离他最远的点的距离：只需要求出任意一个直径，比较两个端点哪个离他比较远就可以了
//2、动态加入叶子，求出直径：根据直径的属性，只需要通过求出(x,now_leaf),(y,new_leaf)去更新(x,y)就可以了
二、中心
//树的中心：该店到树中其他点的距离，最远距离最小（可能有多个）
//已经求出了深度de[]，直径的两个端点x,y,z（lca(x,y))，可以利用树的直径求出树的中心
//设直径长度为R,在x到y的路径上找到与x点距离为R/2的点
int wrok(){
int len=de[x]+de[y]-2*de[z];
if(de[x]-de[z]>len/2){ //该店在x到z的路径上，从x往z找
for(int i=1;i<=len/2;i++) x=fa[x];
return x;
}
for(int i=1;i<=len/2;i++) y=fa[y];//不然就在z到y的路上
return y;
}
三、重心
重心的性质：
（1）重心到其他点的距离和最小，如果有多个重心，那么距离和是一样的
（2）一棵树增加或者减少一个节点，那么重心移动一条边的距离
（2）两棵树通过某个点相连得到一棵新的树，新树的重心一定在连接原来两棵树的重心路径上
//树的重心：无根树，若某个节点的每个儿子的子树大小都小于等于n/2,则这个点叫做该数的重心
//1、先确定一个根，求出以每个点为根的子树大小
//2、枚举每一个节点，看它往下的子树（以每个儿子为根的子树）与往上的子树大小是否都小于等于n/2
int size[maxn],fa[maxn];
int getsi(int x){
si[x]=1;
for(int i=fi[x];i;i=ne[i]){
if(to[i]!=fa[i]){
fa[to[i]]=x;
size[x]+=getsi(to[i]);
}
}
return size[x];
}
bool check(int x){
if(n-si[x]>n/2) return 0;
for(int i=fi[x];i;i=ne[i]){
if((fa[to[i]]==x)&&(size[to[i]]>n/2)) return 0;
}
return 1;
}
//例： 给出一棵有根树，求出每棵子树的重心
//根据重心的性质，从下往上对子树求解，O(N)
bool check(int x,int y){ //检验x是否是子树y的重心
if(size[y]-size[x]>size[y]/2) return 0; //子树x向上的部分
for(int i=fi[x];i;i=ne[i]){
if(si[to[i]]>si[y]/2) return 0; //子树x的每一个子树部分
}
return 1;
}
int bar[maxn];
void getbaryct(int x){
int p=-1;
for(int i=fi[x];i;i=ne[i]){
getbaryct(to[i]); //递归，从下往上
if(size[to[i]]>size[x]/2) p=to[i]; //找到这个size大于x一半的子树，让p指向它 ，重心一定在p到x的路径上
}
if(p==-1) bar[x]=x; //叶子节点
else bar[x]=bar[p] ; //先指向这棵子树的重心，然后不断向上
while(!check(bar[x],x)) bar[x]=fa[bar[x]];
}
- 树形dp的经典问题
1.对于每个点的状态数等于这个点size的一类树形DP，主要就是通过DFS序的应用
void dfs(int x,int fa){
size[x]=1;
for(int i=head[x];i;i=nex[i]){
if(to[i]!=fa){
dfs(to[i],x);
for(int u=0;u<=size[x];u++){
for(int v=0;v<=size[to[i]];v++){
//根据实际情况进行转移
}
}
size[x]+=size[to[i]];
}
}
}
- 树的统计
树上统计各类算法：
1、技巧法
2、启发式合并(dsu on tree) 把小的集合合并到大的集合
3、类长链剖分
4、点分治、边分治
//1、树上所有无序点对之间的距离和
//一条边a,b被经过的次数等与以b为根的子树a的大小乘上以a为根的子树b的大小
int ans=0;
void dfs(int x,int fa){
ans+=size[x]*(n-size[x]);
for(int i=fi[x];i;i=to[i]) if(to[i]!=fa) dfs(to[i]);
}
//2、以1为根节点的树，每个点有一个颜色col[x]，对每个点，有一个询问query[x]，表示求出以x为根的子树中有多少个颜色为query[x]的点
//延伸为，有n个集合，每个集合的大小为1，执行n-1次操作，每次操作任意指定两个大小为a,b的集合，花费Min(a,b)的代价，删去a,b,加入大小为a+b大小的集合
//在DFS的过程中把一个点的所有儿子的信息合并到自身上即可
unordered_map<int,int> mp[maxn]; //mp[x],x是序号，first是颜色，second是集合大小
void merge(int x,int y){
if(mp[x].size()<mp[y].size()) mp[x].swap(mp[y]); //交换，x为集合大的
for(auto u=mp[y]) mp[x][u.first]+=u.second; //把集合y放到集合x上（小的存到大的） 启发式合并
}
void dfs(int x,int fa){
++mp[x][col[x]];
for(int i=fi[x];i;i=ne[i]){
if(to[i]!=fa) {
dfs(to[i],fa)
merge(x,to[i]);
}
}
ans[x]=mp[x][query[x]];
}
//3、以1为根节点的树，对每个点x，都有一个询问query[x]，求出以x为根的子树中有多合距离为query[x]的点
//花费min(x,y)的代价，删去a,b集合，加入大小为max(a,b)+1的集合
//每个点的信息是它子树的信息合并起来加上自己的信息，点代表的集合可以看作是它子树中不同深度的个数，最大深度减去自己的深度
unordered_map<int,int> mp[maxn];
void merge(int x,int y){
if(mp[x].size()<mp[y].size()) mp[x].swap(mp[y]); //交换，x为集合大的
for(auto u=mp[y]) mp[x][u.first]+=u.second; //把集合y放到集合x上（小的存到大的） 启发式合并
}
void dfs(int x,int fa,int de){
++mp[x][de]; //对应的深度个数++
for(int i=fi[x];i;i=ne[i]){
if(to[i]!=fa){
dfs(to[i],x,de+1);
merge(x,to[i]);
}
}
ans[x]=mp[x][de+query[x]];
}