树上问题

树上问题

1. 树的遍历

• 常见方式：先序、中序、后序、层序。
• 作用：访问树上所有结点，为后续统计高度、子树大小等打基础。



类别定义



树的遍历就是：把树上每个结点都访问一遍，并且访问的顺序不同，会形成不同的遍历方式。

• 先序：先访问自己，再访问孩子
• 后序：先访问孩子，再访问自己
• 层序：一层一层访问（BFS）



鉴别方法



• 题目说：“请输出遍历序列”
• 题目需要“遍历所有点”做统计（子树大小、深度、父子关系等）
• 题目是二叉树，问先序/中序/后序互相转化



思路技巧



• 树上很多统计都在 后序 做：因为后序能保证“孩子信息算完，父亲再算”
• 层序（BFS）适合处理：按层的距离、最短路、层数统计



核心伪代码（树 DFS 遍历）





void dfs(int u, int fa){
    // 先序：进入 u 的这一刻（想要先序输出就在这里输出）
    // visit(u);

    for(int v: adj[u]){
        if(v == fa) continue;   // 防止走回父亲
        dfs(v, u);
    }

    // 后序：离开 u 的这一刻（想要后序统计就在这里做）
    // visit(u);
}





核心伪代码（层序遍历 BFS）





queue<int> q;
q.push(root);
fa[root] = 0;
dep[root] = 0;

while(!q.empty()){
    int u = q.front(); q.pop();
    // visit(u);

    for(int v: adj[u]){
        if(v == fa[u]) continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        q.push(v);
    }
}



------



2. 树的直径



• 定义：树中两点之间的最长简单路径长度。
• 常见做法：两次 DFS / BFS。
• 用途：求最远距离、最长路线等。



类别定义



树的直径就是“树上最远的两点”之间的距离。

• 如果边有权：距离是边权和
• 如果边无权：距离是边数（或点数-1）



鉴别方法



• 问“最长路径”“最远两点”“最大距离”
• 树上跑一次最短路（BFS）找最远点，再从最远点跑一次



思路技巧（两次搜索）



关键结论：
从任意点出发找到的最远点 $A$，一定是某条直径的端点之一。
再从 $A$ 出发找到最远点 $B$，$A\leftrightarrow B$ 的距离就是直径长度。

------



3. 树上 DP



• 在树上做动态规划，一般是“子树信息 → 父结点”。
• 常见信息：子树大小、子树权值和、在子树内选点或选边的最优值等。



类别定义



树上 DP 的典型形式：选一个根，把树变成“父子结构”，然后：

• 每个结点的答案只依赖它的子结点答案
• 所以用 DFS 后序计算：先算子树，再算当前点



鉴别方法



• 题目问“子树”“以某点为根的子树”相关统计
• 题目描述是“每个点和它的孩子之间关系”
• 典型：树上最大独立集、树上最优选点、子树大小/和、树形背包



思路技巧



树上 DP 的写法几乎固定：

1. 选根（通常 1）
2. dfs(u, fa)
3. 先递归所有孩子 v
4. 再把孩子的 dp 合并到 u



核心伪代码（子树大小/子树和）





void dfs(int u,int fa){
    sz[u]=1;                 // 子树至少包含自己
    sum[u]=a[u];             // 子树权值和

    for(int v:adj[u]){
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];        // 合并子树大小
        sum[u]+=sum[v];      // 合并子树权值和
    }
}





核心伪代码





void dfs(int u,int fa){
    // dp0[u]：u 不选的最优值
    // dp1[u]：u 选的最优值
    dp0[u]=0;
    dp1[u]=w[u];

    for(int v:adj[u]){
        if(v==fa) continue;
        dfs(v,u);
        dp1[u] += dp0[v];                 // u 选，则孩子不能选
        dp0[u] += max(dp0[v], dp1[v]);    // u 不选，孩子选不选都行
    }
}



------



4. 换根 DP



• 先选一个根做一遍树上 DP，得到“以这个根为基准”的答案。
• 再通过换根（从父到子传信息），把答案转成“以每个结点为根”的结果。
• 适合：要求“对每个结点都算一遍”但又不能暴力重跑 DP 的题目。



类别定义



换根 DP 就是：你想求“每个点当根时”的答案。

如果暴力做：每个点做一次 DFS，复杂度 $O(n^2)$，会超时。
换根 DP 的目标是：用两次 DFS 在 $O(n)$ 或 $O(n\log n)$ 算出所有点答案。



鉴别方法



• 题目问：对每个结点都输出一个值
• 这个值与“以该结点为根”有关
• 例如：每个点到所有点距离和、每个点作为根时的子树外信息



思路技巧（两遍 DFS）



1. 第一遍 DFS（自底向上）：算“子树内信息”
2. 第二遍 DFS（自顶向下）：把“父亲那边的信息”传给孩子，得到全局答案

常见例子：每个点到所有点距离和

• 第 1 遍算 sz[u] 和 distSum[root]
• 第 2 遍用换根公式：

核心伪代码

void dfs1(int u,int fa){
    // 先算子树信息
    for(int v:adj[u]){
        if(v==fa) continue;
        dfs1(v,u);
        // merge v -> u
    }
}

void dfs2(int u,int fa){
    // 把父亲方向的信息“下发”给孩子
    for(int v:adj[u]){
        if(v==fa) continue;
        // push u -> v（根据题目写换根转移）
        dfs2(v,u);
    }
}