树形动态规划基础：计算子树深度的算法实现

1. 树形DP基础与问题引入

树形动态规划（Tree DP）是算法竞赛中处理树结构问题的核心技巧。与线性DP不同，树形DP需要处理节点间的父子关系，通常采用后序遍历的方式自底向上计算状态。今天我们要解决的第一个经典问题就是计算树的深度。

树的深度定义为从根节点到最远叶子节点的最长路径上的节点数。这个问题看似简单，但却是理解树形DP思想的最佳切入点。在实际比赛中，类似的问题变形经常出现在区域赛和ICPC题目中。

2. 问题分析与建模

2.1 题目重述

给定一棵包含n个节点的树（节点编号1~n），其中1号节点为根节点。要求计算每个节点的子树深度。子树深度定义为：以该节点为根的子树中，从该节点到最远叶子节点的路径上的节点数量。

2.2 输入输出格式

输入格式：

• 第一行：整数n（1≤n≤1000），表示节点数
• 接下来n-1行：每行两个整数u和v，表示u是v的父节点

输出格式：

• 输出n行，每行一个整数，表示对应编号节点的子树深度

2.3 树形DP状态定义

对于树形DP问题，关键在于：

1. 合理定义状态
2. 确定转移方程
3. 设计遍历顺序

定义dp[u]表示以u为根的子树深度。根据树的性质，u的子树深度等于其所有子节点子树深度的最大值加1：

dp[u] = max(dp[v1], dp[v2], ..., dp[vk]) + 1
其中v1...vk是u的所有子节点

3. 算法实现详解

3.1 数据结构选择

使用邻接表存储树结构是最常见的选择：

cpp复制const int N = 1010;
vector<int> edges[N]; // edges[u]存储u的所有子节点

对于本题，由于明确给出了父节点关系，也可以选择只记录子节点。如果题目给出的是无向边，则需要添加双向边并在DFS时记录父节点避免回溯。

3.2 深度优先搜索实现

递归实现是最直观的方式：

cpp复制int dfs(int u) {
    int max_depth = 1; // 至少包含自己
    for (int v : edges[u]) {
        max_depth = max(max_depth, dfs(v) + 1);
    }
    return