樹的直徑

什么是樹的直徑？樹的直徑是樹上最長的一條鏈，當然這條鏈并不唯一，所以一棵樹可能有多條直徑。直徑由兩個頂點u、v來決定，若由一條直徑（u,v)，則滿足一下性質：

1）u、v的度數均為1；

2）在任意一個點為根的樹上，u、v必然存在一個點作為最深的葉子節點。深度就是點距離根節點的距離。

如圖所示：

?樹的直徑有兩種求法：第一種就是“跑兩遍dfs”;第二種就是樹形dp。

由于直徑端點u、v必然存在一個是深度最深的點，那么我們可以在以任意節點為根地樹上跑一次dfs求所有點的深度，選取深度最大的點（可能有多個，任取一個）就是v。

于是就可以得到兩個端點u、v，從而確定樹的直徑，其長度就是路徑上點的個數，也就等于以u為根的樹中的dep[v]。

習題：1.賣樹 - 藍橋云課

代碼：

#include<bits/stdc++.h>
using namespace std;using ll = long long;
const int N = 1e5 + 9;
vector<int>g[N];int dep1[N], depu[N], depv[N];void dfs(int x, int fa, int dep[]) {dep[x] = dep[fa] + 1;for (const auto& y : g[x]) {if (y == fa)continue;dfs(y, x, dep);}
}void solve() {ll n, k, c; cin >> n >> k >> c;for (int i = 1; i < n; ++i) {int u, v; cin >> u >> v;g[u].push_back(v), g[v].push_back(u);}dep1[0] = depu[0] = depv[0] = -1;dfs(1, 0, dep1);int u = 1;for (int i = 1; i <= n; ++i) if (dep1[i] > dep1[u]) u = 1;dfs(u, 0, depu);int v = 1;for (int i = 1; i <= n; ++i) if (depu[i] > depu[v])v = i;dfs(v, 0, depv);ll ans = 0;for (int i = 1; i <= n; ++i) {ans = max(ans, max(depu[i], depv[i]) * k - dep1[i] * c);}cout << ans << endl;for (int i = 1; i <= n; ++i) g[i].clear();
}int main() {int t; cin >> t;while (t--) {solve();}return 0;
}

樹的重心

樹的重心是指某個點，將其刪除后，可以使得剩余聯通塊的大小大的點。

也就等價于以某個點為根的樹，將根刪除后，剩余的若干顆子樹的大小最小。

性質：

性質一

重心的若干顆子樹的大小一定<=n;

除了重心以外的所有其他點，都必然存在一顆節點個數>n的子樹。?

性質二

一棵樹至多有兩顆重心，如果存在兩個重心，則必然相鄰；

將連接兩個重心的邊擦除后，一定劃分為兩顆大小相等的樹；

性質三

樹種所有點到某個點的距離和中，到重心的距離和是最小的；

如果有兩個重心，那么它們的距離和一樣。反過來，距離和最小的點一定是重心。

最后，樹的重心問題可以處理一些最優化、最小化問題。

如何求解樹的重心？？？

模板：

void dif(int x, int y) {f[x] = 1, m[x] = 0;for (const auto& z : g[x]) {if (z == y) continue;dif(z, x);f[x] += f[z];m[x] = max(m[x], f[x]);}m[x] = max(m[x], n - f[x]);if (m[x] <= n / 2) v.push_back(x);
}