dfs写法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int n;
int h[N];
int e[N];
int ne[N];
int idx;   // 下标索引

/*
*由于题目中是从 2 至 N 号点进行输入的。
*这里我把下标索引也改成了从 2 至 N 。
*导致节点下标索引和节点值一样。
*/
void add(int a, int b)
{
    e[b] = b;      // 当前边的终点为b
    ne[b] = h[a];  // 新边的next指针指向节点a的第一个子节点
    h[a] = b;      // 更新节点a的第一个子节点索引
}

// 深度优先搜索计算以x为根的子树的最大高度
int dfs(int x)
{
    int res = 0, cnt = 0; // res记录子节点的最大高度，cnt记录子节点数量
    for (int i = h[x]; i != -1; i = ne[i]) // 遍历所有子节点
    {
        cnt ++;                 // 子节点计数
        res = max(res, dfs(i)); 
        //由于我的节点下标索引和节点值一样，所以dfs()中可以填e[i]或者i
        // 递归计算子节点的高度并更新最大值
    }

    return res + cnt; // 当前节点的高度 = 子节点数 + 子节点中的最大高度
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for (idx = 2; idx <= n; idx ++)
    {
        int a;
        scanf("%d", &a);
        add(a, idx);
    }

    cout << dfs(1) << endl;

    return 0;
}

核心算法

1. 邻接表建树：使用数组模拟邻接表存储多叉树结构

2. 深度优先搜索(DFS)：递归计算每个节点的最大高度

3. 动态规划思想：每个节点的高度 = 子节点数量 + 最大子树高度

分析过程

1. 问题转化：将多叉树转换为二叉树时，最大高度取决于：

   • 将子节点最多的分支放在最右侧

   • 其余子节点作为该分支的左侧兄弟

2. 递归关系：

   • 对于节点u，其高度 = 子节点数 + 最深子树高度

   • 即height[u] = count_children(u) + max(height[child])

3. 关键观察：

   • 最优解需要将最深的子树放在兄弟链的最末端

   • 这样该子树的深度可以累加所有兄弟节点的高度

数学思想

1. 递归方程：

$$height(u) = \sum_{v \in children(u)} 1 + \max_{v \in children(u)} height(v)$$

1. 贪心选择：总是将最深的子树放在最后处理，使得路径最长

时间复杂度

• 建树：O(N)，每个节点处理一次

• DFS遍历：O(N)，每个节点访问一次

• 总复杂度：O(N)，线性时间复杂度

应用场景

1. 树形结构转换问题

2. 需要最大化二叉树高度的场景

3. 处理层级关系数据（如组织结构、目录结构）

4. 编译器语法树优化

5. 游戏场景的层次渲染优化

dp写法

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;  // 定义最大节点数，1e5 + 10是为了防止数组越界

int n;                   // 存储节点总数
vector<int> v[N];        // 邻接表，v[i]存储节点i的所有子节点
int dp[N];               // dp数组，dp[i]表示以节点i为根的子树转换后的最大高度

int main()
{
    // 输入节点总数
    scanf("%d", &n);

    // 构建树结构，节点编号从2到n
    for (int i = 2; i <= n; i ++)
    {
        int a;
        scanf("%d", &a);        // 输入当前节点的父节点
        v[a].push_back(i);      // 将当前节点加入父节点的子节点列表
    }

    // 自底向上动态规划处理每个节点
    // 从n到1逆序处理，确保处理父节点时其子节点都已处理完毕
    for (int i = n; i >= 1; i --)
    {
        int max_count = v[i].size();  // 当前节点的子节点数量
        // 遍历所有子节点，更新dp[i]
        for (auto x : v[i])
            // 状态转移方程：
            // 当前节点的高度 = max(当前高度, 子节点高度 + 子节点数量)
            dp[i] = max(dp[i], dp[x] + max_count);
    }

    // 输出根节点1的最大高度
    printf("%d", dp[1]);

    return 0;
}

代码注释详解

1. 数据结构定义

   • const int N = 1e5 + 10：定义最大节点数，预留空间防止越界

   • vector<int> v[N]：邻接表存储树结构，v[i]存储节点i的所有子节点

   • int dp[N]：动态规划数组，dp[i]存储以i为根的子树转换后的最大高度

2. 输入处理

   • scanf("%d", &n)：读取节点总数

   • for (int i = 2; i <= n; i++)：从2号节点开始构建树结构

   • v[a].push_back(i)：将当前节点i添加到父节点a的子节点列表中

3. 动态规划处理

   • for (int i = n; i >= 1; i--)：逆序处理节点，确保子节点先处理

   • max_count = v[i].size()：获取当前节点的子节点数量

   • dp[i] = max(dp[i], dp[x] + max_count)：核心状态转移方程

4. 输出结果

   • printf("%d", dp[1])：输出根节点的最大高度

核心算法说明

该算法采用自底向上的动态规划方法计算多叉树转换为左孩子右兄弟二叉树后的最大高度。关键点在于：

1. 状态定义：dp[i]表示以i为根的子树的最大高度

2. 状态转移：对于每个节点i，其高度等于：

   • 子节点数量（决定右兄弟链长度）

   • 加上子树中的最大高度（决定纵向深度）

3. 处理顺序：逆序处理确保子节点先计算

时间复杂度分析

• 构建树结构：O(N) 每个节点处理一次

• 动态规划处理：O(N) 每个节点和边各访问一次

• 总复杂度：O(N) 完美支持1e5规模的数据

应用场景扩展

1. 文件系统目录：计算最深嵌套目录层级

2. 组织架构图：确定最长汇报链

3. 依赖关系图：分析最长依赖路径

4. UI组件树：计算最大嵌套深度

$$\text{应用公式}：\text{dp}[i] = \max(\text{dp}[x] + \text{child\_count}) \quad \forall x \in \text{children}[i]$$