引入

樹是一種特殊的圖，因其看起來像一顆倒掛的樹而得名。
樹有許多等價的形式化定義，我們這里只取一個：$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]];}
}