注意：为了方便，总结中说的某个点 $x$ 的子树为以 $x$ 为根的子树。

一、树的简介及基本算知识点

1.树的定义

有 $n$ 个点 $n-1$ 条边的图即为树，天生具有拓扑序，所以和 $dp$ 有不解之缘。

2.树的直径（树的直径）

例题

树的直径就是树中最长的简单路径路径的长度。
首先随便选一个点当根，接下来有两种求法，一个为递推一个为分治。

(1)、DFS 做法

做法就是找到一个点 $x$，求出离它最远的点 $y$，$y$ 就是某条直径的一端，再求出离 $y$ 最远的点和距离，这个距离就是树的直径，求最远的点与距离使用 $DFS$。

const int MAXN = 2e5 + 5;

int n, u, x, y, len;
vector<int> g[MAXN];

void Dfs(int x, int fa, int s){
  if(len < s){  // 更新答案
    len = s, u = x;
  }
  for(int y : g[x]){
    if(y != fa){    
      Dfs(y, x, s + 1);
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i < n; i++){
    cin >> x >> y;
    g[x].push_back(y), g[y].push_back(x);
  }
  Dfs(1, 0, 0);
  len = 0;
  Dfs(u, 0, 0);
  cout << len;
  return 0;
}

(2)、分治做法

首先随便找到一点，把它当做根，这个直径一定有个深度最低的点 $x$，那么在以 $x$ 为子树的直径 $dp[x]$ 就是所有以 $y(y \in son[x])$ 的子树里中离 $y$ 最远的点与 $y$ 的距离的最大和次大相加再加 2。
所以看出要记录最大和次大值，重新定义 $dp$ 数组，$dp[0 / 1][x]$ 为所有所有以 $y(y \in son[x])$ 的子树中离 $y$ 最远的点与 $x$ 的距离的最大和次大值，所以每次求出 $dp[0 / 1][x]$， $x$ 为根子树且深度最点为 $x$ 的答案 $= dp[0][x] + dp[1][x]$，把每个点的答案取最大值就是最终答案。
注意：并不是直径一定经过根，如下图，直径为 6 -> 4 -> 2 -> 3 -> 5

const int MAXN = 2e5 + 5;

int n, x, y, ans, dp[2][MAXN];
vector<int> g[MAXN];

void Dfs(int x, int fa){
  for(int y : g[x]){
    if(y != fa){
      Dfs(i, x);
      //更新答案
      if(dp[0][y] + 1 > dp[0][x]){
        dp[1][x] = dp[0][x], dp[0][x] = dp[0][y] + 1;
      }else if(dp[0][y] + 1 > dp[1][x]){
        dp[1][x] = dp[0][y] + 1;
      }
    }
  }
  ans = max(ans, dp[0][x] + dp[1][x]);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i < n; i++){
    cin >> x >> y;
    g[x].push_back(y), g[y].push_back(x);
  }
  Dfs(1, 0);
  cout << ans;
  return 0;
}

时间复杂度：每个点遍历一次，$n - 1$ 条边，总时间复杂度 $O(n)$。

3.树的重心

例题

随便找个点当根，令 $cnt[x]$ 为去掉 $x$ 后剩下的点形成所有树的点的数量的最大值，$cnt[x]$ 最小的就是重心（可能有多个重心）。
做法：去掉了 $x$ 后，它的每个儿子的子树都会独立成一棵树，还有一棵树就是整个树去掉 $x$ 的子树后的一棵树。
令 $sz[x]$ 为 $x$ 的子树的点的数量，则 $$cnt[x] = \max(\max_{y \in son[x]}{sz[y]}, n - sz[x])$$，求出 $cnt[x]$ 最小的点即可。

const int MAXN = 2e5 + 5;

int n, x, y, ans = MAXN, sz[MAXN], cnt[MAXN];
vector<int> g[MAXN];

void Dfs(int x, int fa){
  for(int y : g[x]){
    if(y != fa){
      Dfs(y, x);
      sz[x] += sz[y], cnt[x] = max(cnt[x], sz[y]);
    }
  }
  sz[x]++, cnt[x] = max(cnt[x], n - sz[x]), ans = min(ans, cnt[x]);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i < n; i++){
    cin >> x >> y;
    g[x].push_back(y), g[y].push_back(x);
  }
  Dfs(1, 0);
  for(int i = 1; i <= n; i++){
    if(cnt[i] == ans){
      cout << i << '\n';
    }
  }
  return 0;
}

时间复杂度：每个点遍历一次，$n - 1$ 条边，总时间复杂度 $O(n)$。

实际应用

题目1：CSES P1113

题意

给定一个 $n$ 个结点的树，请你求出从每个结点出发到达其他所有结点的距离和。
$1 \le n \le 2 \times 10 ^ 5$

思路

(1)、暴力

枚举每个点当成根，让其变为有根树。
令 $sum[x]$ 为 $x$ 的子树中所有点到 $x$ 的距离和，$sz[x]$ 为 $x$ 的子树的点的数量，则 $$sum[x] = \sum_{y \in son[x]}{sum[y] + sz[y]}$$，就求出了根到每个点的距离和。
时间复杂度：每次花 $O(n)$ 求答案，共 $n$ 次，总时间复杂度：$O(n^2)$。

(2)、换根

首先先把 1 当做根，做一次暴力中的操作。
令 $dp[x]$ 为 $x$ 到所有点的距离，$dp[1] = sum[1]$。
如果知道了 $dp[x]$，则 $dp[y](y \in son[x])$，也可求出，可以观察下图，下图就是在换根。红色部分为 $y$ 的子树的贡献，蓝色部分是剩余部分到 $x$ 的距离和，然后剩余部分到 $y$ 的距离和还要加上黄色部分。化简后得：$dp[y] = dp[x] + n - 2·sz[y]$(图片右下角为 $sz[y]$)。

时间复杂度：做了一次暴力中的操作：$O(n)$，枚举每个点求答案：$O(n)$，总时间复杂度：$O(n)$。

using ll = long long;

const int MAXN = 2e5 + 5;

ll dp[MAXN];
int n, x, y, sz[MAXN];
vector<int> g[MAXN];

//求 dp[1]
ll Dfs1(int x, int fa){
  ll sum = 0;
  for(int y : g[x]){
    if(y != fa){
      sum += Dfs1(y, x) + sz[y], sz[x] += sz[y];
    }
  }
  sz[x]++;
  return sum;
}

//枚举每个点
void Dfs2(int x, int fa){
  for(int y : g[x]){
    if(y != fa){
      dp[y] = dp[x] + n - 2 * sz[y]; //求答案
      Dfs2(y, x);
    }
  }
}

int main(){
  ios::sync_with_stdio(0),cin.tie(0);
  cin >> n;
  for(int i = 1; i < n; i++){
    cin >> x >> y;
    g[x].push_back(y), g[y].push_back(x);
  }
  dp[1] = Dfs1(1, 0), Dfs2(1, 0);
  for(int i = 1; i <= n; i++){
    cout << dp[i] << ' ';
  }
  return 0;
}

JZTXT

树总结

一、树的简介及基本算知识点

1.树的定义

2.树的直径（树的直径）

例题

3.树的重心

例题

实际应用

题目1：CSES P1113

题意

思路

(1)、暴力

(2)、换根