树形动态规划：如何高效计算节点深度和

1. 题目分析与解题思路

这道题目要求我们在一个树结构中找到这样一个根节点：当以该节点为根时，树中所有节点的深度之和达到最大值。理解这个问题的关键在于掌握树的性质和动态规划的应用。

1.1 树的基本性质

树是一种无向无环连通图，具有以下重要特性：

• 任意两个节点之间有且只有一条路径
• 边数 = 节点数 - 1
• 删除任意一条边都会使图不再连通
• 添加任意一条边都会形成环

在本题中，我们需要利用树的一个重要性质：当改变树的根节点时，可以通过父节点和子节点之间的关系快速计算出新的深度和，而不需要每次都重新遍历整棵树。

1.2 深度和的计算原理

深度和指的是树中所有节点到根节点的距离之和。直接计算每个节点作为根时的深度和时间复杂度是O(n²)，对于n=10⁶的数据规模显然不可行。

更高效的方法是：

1. 先以任意节点（如节点1）为根，计算每个节点的深度和子树大小
2. 然后通过动态规划的方式，利用父节点的信息推导子节点的深度和

这个方法的巧妙之处在于利用了树结构的递归性质，通过两次深度优先搜索（DFS）就能完成计算，时间复杂度降为O(n)。

2. 算法实现详解

2.1 第一次DFS：预处理

cpp复制void dfs1(int x) {
    size[x] = 1;  // 初始化子树大小为1（包含自己）
    vis[x] = 1;   // 标记已访问
    for(int i=0; i<son[x].size(); i++) {
        int v = son[x][i];
        if(!vis[v]) {
            dep[v] = dep[x] + 1;  // 子节点深度=父节点深度+1
            dfs1(v);
            size[x] += size[v];   // 累加子树大小
        }
    }
}

这个DFS完成三个任务：

1. 计算每个节点的深度（dep数组）
2. 计算每个节点的子树大小（size数组）
3. 标记已访问节点防止重复计算

注意：这里使用vis数组而不是传统的父节点检查方法，是为了避免在后续的第二次DFS中混淆访问状态。

2.2 第二次DFS：动态规划转移