换根DP：树形动态规划的高效优化技巧-云帆数科

1. 换根DP的核心思想与应用场景换根DP也称为二次扫描法是树形动态规划中的一种特殊技巧主要用于解决需要以不同节点为根进行多次计算的问题。这类问题的典型特征是我们需要对树中的每个节点作为根的情况进行计算但直接暴力枚举每个节点作为根会导致O(n²)的时间复杂度这在处理大规模树结构时如n1e6显然不可行。换根DP的精妙之处在于它通过两次深度优先搜索DFS将时间复杂度优化到O(n)第一次DFS以任意节点通常选择1号节点为根计算子树相关信息第二次DFS利用父节点的信息推导子节点的信息实现换根操作这种技巧在以下场景特别有用需要找到使某种树指标最优的根节点如最大深度和、最小代价等需要对每个节点作为根时计算全局性质树结构动态变化时需要快速重新计算全局信息提示换根DP不是一种独立的算法而是对常规树形DP的优化技巧。掌握它需要先熟悉基础的树形DP和DFS遍历。2. 洛谷P10962问题解析2.1 题目重述与理解原题描述为给定一棵N个节点的树找出一个节点作为根使得所有节点的深度之和最大。其中节点深度定义为到根节点的距离边数树是无向无环连通图典型数据范围N ≤ 1e6这个问题如果采用暴力解法对每个节点作为根进行一次DFS计算深度和时间复杂度为O(n²)对于n1e6显然会超时1e12次操作。这正是换根DP大显身手的场景。2.2 暴力解法的局限性让我们先看看暴力解法的伪代码max_sum -inf best_root None for each node u in tree: total 0 perform DFS/BFS with u as root: for each node v: total depth[v] if total max_sum: max_sum total best_root u这种解法的问题在于每次换根都重新计算所有节点的深度没有利用之前计算的信息对于每个节点都进行O(n)的遍历整体O(n²)复杂度在树结构不变的情况下存在大量重复计算3. 换根DP的数学推导3.1 定义关键变量我们需要定义几个关键变量来帮助推导sz[u]以u为根的子树大小节点数dep[u]在初始根通常为节点1下的深度f[u]以u为根时的深度和即我们要求的量3.2 第一次DFS预处理第一次DFS以节点1为根计算两个基本信息每个节点的子树大小sz[u]每个节点到根节点的深度dep[u]同时我们可以计算出f[1]以1为根时的深度和def dfs1(u, parent): sz[u] 1 for v in children of u: if v parent: continue dep[v] dep[u] 1 dfs1(v, u) sz[u] sz[v] f[1] dep[u] # 累加所有节点的深度3.3 第二次DFS换根转移这是换根DP的核心部分。当我们从父节点u转移到子节点v时如何快速计算f[v]关键观察当根从u变为v时v的子树中所有节点的深度都减1因为它们离根更近了不在v子树中的节点深度都加1因为它们离根更远了因此转移方程为f[v] f[u] - sz[v] (n - sz[v])简化为f[v] f[u] n - 2 * sz[v]实现代码def dfs2(u, parent): for v in children of u: if v parent: continue f[v] f[u] n - 2 * sz[v] dfs2(v, u)4. 完整算法实现与优化4.1 C完整代码示例#include iostream #include vector using namespace std; const int MAXN 1e6 5; vectorint tree[MAXN]; int sz[MAXN], dep[MAXN]; long long f[MAXN]; int n; void dfs1(int u, int parent) { sz[u] 1; for (int v : tree[u]) { if (v parent) continue; dep[v] dep[u] 1; dfs1(v, u); sz[u] sz[v]; } } void dfs2(int u, int parent) { for (int v : tree[u]) { if (v parent) continue; f[v] f[u] n - 2 * sz[v]; dfs2(v, u); } } int main() { cin n; for (int i 1; i n; i) { int u, v; cin u v; tree[u].push_back(v); tree[v].push_back(u); } dfs1(1, 0); for (int i 1; i n; i) f[1] dep[i]; dfs2(1, 0); long long max_sum -1; int best_root 0; for (int i 1; i n; i) { if (f[i] max_sum) { max_sum f[i]; best_root i; } } cout best_root endl; return 0; }4.2 算法复杂度分析时间复杂度O(n)两次DFS都是O(n)的遍历最后的查找最大值也是O(n)空间复杂度O(n)存储树结构O(n)各种数组O(n)4.3 边界条件与注意事项树的存储对于大规模数据n1e6务必使用邻接表而非邻接矩阵数据类型深度和可能很大n²级别使用long long而非int初始根选择理论上可以选择任意节点作为初始根但通常选择1号节点最方便递归深度对于极端链状树递归DFS可能导致栈溢出可以改用BFS或显式栈实现5. 相关例题与变式5.1 洛谷P2986 [USACO10MAR] Great Cow Gathering题目变式每个节点有牛的数量c[i]边有长度w求使所有牛到根的总距离最小的根节点。解法调整sz[u]改为子树中牛的总数转移方程变为f[v] f[u] (total_cows - 2 * sz[v]) * w(u,v)5.2 洛谷P3047 [USACO12FEB] Nearby Cows题目特点对每个节点求距离不超过k的节点权值和。解法思路定义f[u][k]为以u为根距离不超过k的和第一次DFS计算子树贡献第二次DFS合并父亲节点的贡献注意去重处理5.3 实战技巧总结换根DP的通用思考步骤确定要计算的信息设计第一次DFS计算的子树信息推导换根时的转移方程实现第二次DFS完成信息传递常见错误忘记处理父节点与子节点的关系导致循环调用转移方程推导错误数据类型范围不足调试技巧先用小样例验证打印中间结果检查对比暴力解法的结果在实际编程竞赛中换根DP是一个强大的工具掌握它可以在处理树形问题时游刃有余。建议通过大量练习来熟悉各种变式和技巧。

企业数字化 ERP 产品动态

相关推荐

Kafka消息队列消费幂等性实现与实践指南

1. 消息队列消费幂等性基础概念在分布式系统中，消息队列作为解耦生产者和消费者的中间件，其可靠性保障机制尤为重要。幂等性(Idempotence)是指对同一个操作执行多次产生的结果与执行一次的结果相同。在消息消费场景中，这意味着无论同一条消息… · 2026/11/3 21:50:03

Hadoop分布式集群规划与性能优化实战指南

1. 大数据分布式集群概述大数据分布式集群是现代数据处理的核心基础设施，它通过将计算和存储任务分散到多台服务器上协同工作，解决了单机系统在容量和性能上的瓶颈。一个典型的Hadoop集群由NameNode、DataNode、ResourceManager和NodeManager等核心组件构… · 2026/11/4 8:58:00

AI工程体系从零构建：Python/TS/Rust/Julia四语言协同架构

1. 为什么“从零构建AI工程体系”不是写个Python脚本那么简单很多人看到“AI Engineering from Scratch”这个标题，第一反应是：不就是用PyTorch搭个模型、跑通一个MNIST分类器？再加点Flask接口，扔到Docker里——完事。我去年也这么… · 2026/11/2 17:53:45

括号匹配为什么用栈：有效括号判断的原理与工程实践

简介：这是一份围绕括号匹配（平衡括号）判定编写的 JavaScript 代码示例包，面向正在学习字符串处理与栈结构的初学者，以及准备算法面试的开发者，用于解决“左括号须由同类型右括号按正确顺序闭合”的有效性判… · 2026/11/4 8:59:37

MoBaiTool系统优化六模块：CPU调校、电源方案与大小核调度实战

装完系统、驱动打完、跑分漂亮，结果一上手就发现不对劲：风扇隔几分钟就窜一下、点开浏览器要愣半秒、笔记本拔了电源续航直接腰斩、游戏帧数忽高忽低还带轻微卡顿。这类问题八成不是硬件坏了，而是系统里一堆默认开关没人管。系统优化工具箱Mo… · 2026/11/4 8:59:37

AI Agent专属文件柜：会话隔离、临时凭证与生命周期设计

1. 为什么 AI Agent 需要一个专属文件柜 1.1 Agent 的记忆困境：上下文窗口装不下一整个世界我带的团队今年上半年接了三个跟 AI Agent 相关的项目，从客服工单分流做到内部知识助手，再到一个跨境电商的商品图处理流水线。这三个项目在架构上… · 2026/11/4 8:59:37

智算集群性能监控与NCCL故障诊断实战指南

1. 从一次训练任务卡死说起：智算集群为什么需要“听诊器”凌晨两点，训练任务突然卡在某个 step 不动了。日志没有报错，GPU 利用率从 95% 掉到 3%，nvidia-smi 显示显存还占着，但计算流已经停了。这种场景，搞… · 2026/11/4 8:59:37

Hive数据清洗实战：从原理到优化的完整指南

1. 项目概述：Hive数据清洗的核心价值在数据驱动的决策时代，企业数据仓库中往往堆积着大量原始、杂乱甚至错误的数据。作为Hadoop生态系统中使用最广泛的数据仓库工具，Hive承担着将原始数据转化为可用信息的重任。但实际情况是，我… · 2026/11/4 8:59:37

2026年AI工程化十大热门岗位：推理加速、Agent开发与端侧部署技能全解析

1. 从招聘需求倒推：这10个岗位为什么会在2026年集中爆发过去大半年，我一直在跟踪国内外AI团队的招聘JD变化，也帮几个朋友做过内推和简历诊断。一个很明显的感受是：2024年大家还在抢“大模型训练工程师”，到了2025年下… · 2026/11/4 8:58:36

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49