树的重心

树的重心（也称为树的质心）是指这样的一个节点：当我们删除这个节点后，剩余的所有连通块的最大节点数不超过原树总节点数的一半。简单来说，就是去掉该节点后，剩下的子树尽可能地“平衡”。

算法步骤

从树的任意一个节点（通常是节点1）开始进行DFS遍历。

在DFS过程中，执行以下操作：

• 初始化子树大小：将当前节点的子树大小dp[u]初始化为1。
• 标记是否是重心：设置一个布尔变量flag为true，用来标记当前节点是否可能是重心。
• 遍历子节点：遍历当前节点的所有子节点v。
  • 如果子节点v未被访问，则标记为已访问，并递归调用dfs(v)。
  • 更新当前节点的子树大小dp[u]，累加子节点v的子树大小。
  • 如果子节点v的子树大小大于总节点数的一半，则将flag设置为false，因为当前节点不能是重心。
• 检查父节点部分的大小：如果当前节点u的父节点部分的大小（即总节点数减去dp[u]）大于总节点数的一半，则将flag设置为false。
• 记录重心：如果flag仍为true，则当前节点u是一个重心，将其添加到ans数组中，并增加len。

Java实现

查看代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class TreeCentroid {

    private static final int MAXN = 105; // 根据需要调整大小
    private static List<Integer>[] g = new List[MAXN]; // 邻接表
    private static int[] dp = new int[MAXN]; // 存储每个节点的子树大小
    private static boolean[] vis = new boolean[MAXN]; // 访问标记
    private static int[] ans = new int[MAXN]; // 存储找到的重心
    private static int len = 0; // 重心的数量
    private static int n; // 节点数

    // 深度优先搜索函数
    private static void dfs(int u) {
        dp[u] = 1; // 初始化当前节点的子树大小
        boolean flag = true; // 标记是否是重心

        for (int v : g[u]) {
            if (!vis[v]) { // 如果没有访问过
                vis[v] = true;
                dfs(v); // 递归访问子节点
                dp[u] += dp[v]; // 更新当前节点的子树大小
                if (dp[v] > n / 2) { // 如果子树大小超过总节点的一半，则不是重心
                    flag = false;
                }
            }
        }

        if (n - dp[u] > n / 2) { // 如果父节点部分的大小超过总节点的一半，则不是重心
            flag = false;
        }

        if (flag) { // 如果满足条件，则该节点是重心
            ans[++len] = x;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 读取节点数量

        // 初始化邻接表
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }

        // 构建图
        for (int i = 1; i < n; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            g[u].add(v);
            g[v].add(u);
        }

        // 开始DFS寻找重心
        vis[1] = true; // 标记根节点已访问
        dfs(1);

        // 输出结果
        System.out.println(len); // 输出重心的数量
        for (int i = 1; i <= len; i++) {
            System.out.println(ans[i]); // 输出每一个重心
        }

        scanner.close();
    }
}

树的直径

树的直径是树中任意两个节点之间的最长路径的长度。换句话说，它是树中最远的两个节点之间的距离。

算法步骤

1. 第一次DFS：从任意一点P出发，通过DFS寻找离它最远的点Q。
2. 第二次DFS：从点Q出发，通过DFS寻找离它最远的点W。
3. 计算直径：直径即为W到Q的距离。

Java实现

查看代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class TreeDiameter {

    private static final int MAXN = 100005; // 节点数量上限
    private static List<Integer>[] g = new List[MAXN]; // 邻接表
    private static int[] dep = new int[MAXN]; // 存储每个节点的深度
    private static boolean[] vis = new boolean[MAXN]; // 访问标记
    private static int far = 0; // 最远节点
    private static int n; // 节点数

    // 深度优先搜索函数
    private static void dfs(int cur, int d) {
        vis[cur] = true;
        dep[cur] = d;
        if (dep[cur] > dep[far]) {
            far = cur;
        }
        for (int to : g[cur]) {
            if (!vis[to]) {
                dfs(to, d + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 读取节点数量

        // 初始化邻接表
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }

        // 构建图
        for (int i = 1; i < n; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            g[u].add(v);
            g[v].add(u);
        }

        // 第一次DFS，从任意节点（假设是1）开始，找到最远的节点
        dfs(1, 0);

        // 重置访问标记和深度数组
        for (int i = 1; i <= n; i++) {
            vis[i] = false;
            dep[i] = 0;
        }

        // 第二次DFS，从第一次DFS找到的最远节点开始，找到最远的节点
        dfs(far, 0);

        // 输出结果
        System.out.println("Tree Diameter: " + dep[far]);
        scanner.close();
    }
}

树上启发式合并

树上启发式合并适用于解决需要合并子树信息的树结构问题。

蓝桥杯2023年第十四届省赛真题-颜色平衡树

题目描述

给定一棵树，树的结点由 1 至 n 编号，其中结点 1 是树根。每个结点有一个颜色 $C_i$。如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。任务是求出这棵树中有多少个子树是颜色平衡树。

输入格式

• 第一行包含一个整数 $n$，表示树的结点数。
• 接下来 n 行，每行包含两个整数 $C_i$ 和 $F_i$，用一个空格分隔，分别表示第 $i$ 个结点的颜色和父亲结点编号。
• 特别地，输入数据保证 $F_1$ 为 0，也即 1 号点没有父亲结点。输入数据保证构成一棵树。

输出格式

• 输出一行，包含一个整数，表示颜色平衡子树的数量。

算法步骤

1. 重链剖分(Heavy-Light Decomposition, HLD)：将树分解成若干条重链和轻链，其中重链是指子树大小最大的链。这样可以保证在进行信息合并时，每次合并的操作次数尽可能少。
2. DFS序：通过DFS遍历树，计算每个节点的子树大小，并找到每个节点的重儿子。
3. 信息合并：在DFS遍历过程中，合并子树的信息到父节点。合并时，总是先处理轻儿子，再处理重儿子。
4. 延迟更新：在合并信息时，可以使用延迟更新的技巧来优化性能。

Java实现

查看代码

import java.util.*;

public class TreeHeuristicMerge {
    private static final int MAX_N = 200005;
    private static int[] col = new int[MAX_N]; // 节点颜色
    private static int[] par = new int[MAX_N]; // 父节点
    private static List<Integer>[] g = new ArrayList[MAX_N]; // 树的邻接表表示
    private static int ans = 0; // 总答案
    private static int[] hson = new int[MAX_N]; // 重儿子
    private static int[] siz = new int[MAX_N]; // 子树大小
    private static Map<Integer, Long> freq = new HashMap<>(); // 颜色频率映射

    static {
        for (int i = 0; i < MAX_N; i++) {
            g[i] = new ArrayList<>();
        }
    }

    // 计算每个子树的大小并找到重儿子
    private static void dfsSiz(int u, int p) {
        siz[u] = 1;
        int maxSiz = 0;
        for (int v : g[u]) {
            if (v == p) continue;
            dfsSiz(v, u);
            siz[u] += siz[v];
            if (siz[v] > maxSiz) {
                maxSiz = siz[v];
                hson[u] = v;
            }
        }
    }

    // 将子树的颜色频率加入到映射中
    private static void addFreq(int u, int p) {
        freq.put(col[u], freq.getOrDefault(col[u], 0L) + 1);
        for (int v : g[u]) {
            if (v == p) continue;
            addFreq(v, u);
        }
    }

    // 从映射中移除子树的颜色频率
    private static void removeFreq(int u, int p) {
        freq.put(col[u], freq.get(col[u]) - 1);
        if (freq.get(col[u]) == 0) {
            freq.remove(col[u]);
        }
        for (int v : g[u]) {
            if (v == p) continue;
            removeFreq(v, u);
        }
    }

    // 深度优先搜索解决题目
    private static void dfsUnion(int u, int p, boolean keep) {
        for (int v : g[u]) { // 处理轻儿子
            if (v == p || v == hson[u]) continue;
            dfsUnion(v, u, false);
        }
        if (hson[u] != 0) { // 处理重儿子
            dfsUnion(hson[u], u, true);
        }
        freq.put(col[u], freq.getOrDefault(col[u], 0L) + 1); // 更新当前节点的颜色频率
        for (int v : g[u]) { // 更新轻儿子的颜色频率
            if (v == p || v == hson[u]) continue;
            addFreq(v, u);
        }
        long freqVal = freq.values().iterator().next(); // 获取任意一种颜色的频率
        boolean allSame = true; // 标记是否所有颜色频率相同
        for (long val : freq.values()) { // 检查所有颜色频率是否相同
            if (val != freqVal) {
                allSame = false;
                break;
            }
        }
        ans += allSame ? 1 : 0; // 如果颜色频率相同，增加答案计数
        if (!keep) { // 如果不需要保持当前状态，则移除当前节点的颜色频率
            removeFreq(u, p);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            col[i] = in.nextInt();
            par[i] = in.nextInt();
            g[par[i]].add(i);
        }
        dfsSiz(1, -1); // 初始化计算子树大小和重儿子
        dfsUnion(1, -1, true); // 开始处理
        System.out.println(ans); // 输出答案
        in.close();
    }
}

dfsUnion 方法详解

dfsUnion 方法是整个算法的核心部分。

参数:

• u：当前处理的节点。
• p：当前节点的父节点。
• keep：布尔值，指示是否在回溯时保留当前节点的颜色频率信息。

逻辑流程:

1. 处理轻儿子：

   • 对于当前节点 u 的所有子节点 v，如果 v 不是父节点 p 或重儿子 hson[u]，则递归调用 dfsUnion(v, u, false)。这一步确保了所有轻儿子都被处理，且不会保留它们的颜色频率信息。

2. 处理重儿子：

   • 如果当前节点 u 有重儿子 hson[u]，则递归调用 dfsUnion(hson[u], u, true)。这一步确保了重儿子被处理，并且会保留它的颜色频率信息。

3. 更新颜色频率：

   • 将当前节点 u 的颜色加入到频率映射 freq 中。
   • 对于当前节点 u 的所有非父节点 p 和非重儿子 hson[u] 的子节点 v，递归调用 addFreq(v, u)，将这些轻儿子的颜色频率加入到 freq 中。

4. 检查颜色平衡：

   • 获取频率映射 freq 中任意一种颜色的频率 freqVal。
   • 遍历频率映射 freq 中的所有颜色频率值，检查是否所有的频率都等于 freqVal。如果是，则说明当前子树是颜色平衡的，增加答案计数 ans。

5. 回溯清理：

   • 如果 keep 为 false，则调用 removeFreq(u, p)，从频率映射 freq 中移除当前节点 u 及其子树的颜色频率信息。这一步确保了在回溯时不会影响其他路径的颜色频率统计。

换根DP

换根 DP是一种处理树形结构问题的技巧，它通过改变树的根节点并利用之前计算的结果来高效地解决问题。

问题描述

• 输入：一个无根树，由 n 个节点组成。
• 输出：以哪个节点为根时，所有节点的深度和最大。

算法步骤

1. 指定根节点

首先，我们指定树上的某个节点（例如 1 号节点）作为根节点。

2. 第一次搜索（预处理）

从指定的根节点开始进行深度优先搜索（DFS），完成以下预处理：

• 计算每个节点的子树大小。
• 计算以当前根节点为根时，每个节点的深度。
• 计算以当前根节点为根时，所有节点的深度和。

在这次搜索中，我们可以使用一个数组 sz[i] 来记录以 i 为根的子树的大小，使用数组 dp[i] 来记录以 i 为根时，其子树内所有节点的深度和。

3. 第二次搜索（换根）

再次从根节点开始进行 DFS，这次的目标是利用已知的根节点信息来计算其他节点作为根时的深度和。具体步骤如下：

• 对于每个节点 x，我们已经知道以 x 为根的子树大小 sz[x] 和深度和 dp[x]。
• 当我们从节点 x 向其父节点 p 移动时，我们需要更新以 p 为根时的深度和。
• 考虑到将根从 x 移动到 p 时，x 的子树内的所有节点深度减少 1，而 p 的其他子树内的所有节点深度增加 1。

具体更新规则如下：

• 新的 dp[p] 应该是原来的 dp[p] 减去 sz[x]（因为 x 的子树内的节点深度减少了），再加上 (n - sz[x])（因为除了 x 的子树外的其他节点深度增加了）。

用公式表示就是：

dp[p] = dp[p] - sz[x] + (n - sz[x])

Java伪代码

查看代码

void dfs1(int u, int p) {
    sz[u] = 1;
    dp[u] = 0;
    for (int v : g[u]) {
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        dp[u] += dp[v] + sz[v]; // 加上 v 子树内所有节点的深度
    }
}
void dfs2(int u, int p) {
    for (int v : g[u]) {
        if (v == p) continue;
        dp[u] -= dp[v] + sz[v]; // 减去 v 子树内所有节点的深度
        dp[v] += dp[u] + (n - sz[v]); // 更新 v 为根时的深度和
        dfs2(v, u);
        // 恢复 u 的 dp 值，以便于计算其他子节点
        dp[u] += dp[v] + sz[v];
    }
}
int main() {
    // 初始化和输入处理
    dfs1(1, -1); // 第一次 DFS
    dfs2(1, -1); // 第二次 DFS
    // 输出结果
}