引入

树是一种特殊的图，因其看起来像一颗倒挂的树而得名。
树有许多等价的形式化定义，我们这里只取一个：$n$个点$n-1$条边的无向连通图。

树的直径

定义树上任意两点之间最长的简单路径为树的直径。
一棵树可能有很多直径，如菊花图等。

DFS求法

在没有负边权的情况下，我们一般使用两次DFS求树的直径：
第一次DFS从任意位置出发，找到距离起点最远的点$x，x$是一条直径的端点之一;
第二次DFS从点$x$出发，找到距离点$x$最远的点$y$，$x$到$y$的路径即为一条直径。

证明&实现

https://oi-wiki.org/graph/tree-diameter/#%E8%BF%87%E7%A8%8B

树形DP

有负边权的情况下，不能使用DFS求法，这时就需要用到树形DP来求解。
任取一个节点作为根节点，对于每个节点$x$，考虑以$x$为根节点的子树中经过$x$的最长的路径，这个路径长度等于$x$向下的最长路径长度+次长路径长度，DFS时分别记录这些信息即可。

实现

void dfs(int u,int fa){d1[u]=d2[u]=0;     //d1是最长路，d2是次长路for(int v:E[u]){if(v==fa)continue;dfs(v,u);int dv=d1[v]+1;if(dv>d1[u]){d2[u]=d1[u];d1[u]=dv; }else if(dv>d2[u]){d2[u]=dv;}}ans=max(ans,d1[u]+d2[u]);
}

树的重心

选择一个合适的根节点，使得根节点的子树能够尽可能的“均匀”，
这个根节点就是树的重心。
如何量化“均匀”呢，我们这里把最大子树节点数认为是“均匀”的程度，
最大子树节点数越小，就越均匀。使得最大子树节点数最小的根节点，就是重心。

性质

●树的重心最多只有两个，若有两个一定相邻。
●以重心作为根节点，根节点的最大子树节点数不会超过$n/2$
●树上所有点到某个点的距离之和中，到重心的最小。
●把两棵树用一条边连起来，形成的新的树的重心在原来两树重心之间的路径上。
●在一颗树上添加一个叶子节点，重心最多向叶子节点移动一条边。

求法

从任意一点作为根节点出发做DFS，求每个节点的子树节点数，就能知道每个节点作为根节点时的子树大小，向下的子树大小直接统计，向上的子树大小等于$n-size[now]$。

实现

int size[N],mx[N];
void dfs(int u,int fa){for(int v:E[u]){if(v==fa)continue;dfs(v,u);size[u]+=size[v];mx[u]=max(mx[u],size[v]);     // 向下的子树大小}size[u]++;mx[u]=max(mx[u],n-size[u]);    // 向上的子树大小
}

DFS序

树是一种二维的结构，和一维的序列比起来，树的结构更加复杂，我们在思考树上问题的解法时，也常常会先考虑一条链（一维序列）上的情况如何求解。

那么有没有一种方法，可以把一颗二维的树，拍扁压缩降维成一个序列呢？我们按照DFS的顺序，记录每个节点第一次被访问到的时间，这就是树的序列化——DFS序（DFN）。

性质

DFS有一些神奇的性质，比如一颗子树内的每个节点一定都是连续访问的，
所以一颗子树内的节点的DFS序可以用一个区间表示，
结合我们之前学过的区间查询/区间修改，我们就可以在树上做更多操作。

实现

int dfn[N],size[N],id[N],time;
// dfn[i]表示第i个点的dfs序是dfn[i]
// id[i]表示dfs序为i的点是id[i]
// 第i个点的子树的dfn区间如何表示？
// [dfn[i], dfn[i] + size[i] - 1]
void dfs(int u,int fa){dfn[u]=++time;id[time]=u;for(int v:E[u]){if(v==fa)continue;dfs(v,u);size[u]+=size[v];}size[u]++;
}

最近公共祖先（LCA）

两个点的最近公共祖先，就是两点的公共祖先中距离根节点最远的那个点。

暴力求法

两个点中较深的点跳到它自己的父节点，重复该操作直到两点相遇，此时位置即为LCA。
时间复杂度$O(n)$，空间复杂度$O(1)$。

倍增求法

我们可以通过倍增预处理出每个点的$2^k$级祖先，先把两点移动到相同的高度，如果两点不相同，就可以利用倍增数组$log$求得最远的不相同的祖先节点，该点的父节点即为LCA。

int fa[20][N];    // 倍增数组，fa[i][x] 表示x号节点的2^i级祖先
int dep[N];
int lca(int a,int b){
//  while(dep[a]<dep[b])b=fa[0][b];if(dep[a]<dep[b])swap(a,b);const int k=dep[a]-dep[b];for(int i=0;i<=19;i++){if(k>>i&1){a=fa[i][a];}}if(a==b)return a;for(int i=19;i>=0;i--){if(fa[i][a]!=fa[i][b]){a=fa[i][a];b=fa[i][b];}}return fa[0][a];
}

DFN上ST表求法

首先处理出dfn，然后在dfn上建st表维护区间内距离根节点最近的节点。
查询lca时，设最小dfn为$l$，最大dfn为$r$，
只需要查询$[l+1,r]$区间内距离根节点最近的节点，该节点的父节点即为lca。

int dfn[N], size[N], id[N], time, dep[N];
int st[20][N];
void init() {for (int i = 1; i <= n; i++) {st[0][i] = id[i];}for (int i = 1, p = 1; i < 20; i++, p <<= 1) {for (int j = 1; j + p * 2 - 1 <= n; j++) {st[i][j] = dep[st[i-1][j]] < dep[st[i-1][j+p]] ?st[i-1][j] : st[i-1][j+p];}}
}
int lca(int a, int b) {if (a == b) return a;int l = dfn[a], r = dfn[b];if (l > r) swap(l, r);
//    [l + 1, r]l++;int len = r - l + 1;int k = lg2[len];if (dep[st[k][l]] < dep[st[k][r-(1<<k)+1]]) {return fa[st[k][l]];} else {return fa[st[k][r-(1<<k)+1]];}
}