树的定义构造模板

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
vector<int> adj[N];  // 邻接表
int parent[N], depth[N];

void buildTree(int n) {
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

// DFS 遍历求深度和父节点
void dfs(int u, int fa) {
    parent[u] = fa;
    depth[u] = depth[fa] + 1;
    for (int v : adj[u]) {
        if (v != fa) dfs(v, u);
    }
}

int main() {
    int n;
    cin >> n;
    buildTree(n);
    dfs(1, 0);  // 以1为根

    for (int i = 1; i <= n; i++)
        cout << i << ": depth=" << depth[i] << " parent=" << parent[i] << endl;
    return 0;
}

📖 要点说明

• 邻接表 vector<int> adj[N] 是存树的标准方式
• 树有 n-1 条边，无环连通图
• DFS/BFS 都可遍历，DFS 更适合递归场景

⚠️ 常见错误

• DFS 忘传父节点导致来回跳（死循环）
• 节点编号从0还是1开始搞混
• 忘处理 n=1 的边界情况