换根DP不能局部更新，因其依赖全局静态的子树大小sz[]和固定树结构；边权或结构变动需重算受影响子树sz[]并重新传播，点权修改若不改变子树统计则可能微调，但删边/加边必须重建整个换根过程。
dfs1 和 dfs2 已经做完，答案数组 ans[] 也初始化好了——这时候你改了一个点的权值、删了一条边、或者树结构动态变了，还想让所有 ans[u] 保持正确，但又不想再跑两遍 DFS。问题很实际：换根DP的答案能不能局部更新？
不能直接局部更新，除非你把换根DP“拆解”成可维护的结构。
换根DP本质是两次静态DFS，不是在线数据结构
dfs1 算子树大小 sz[u]、深度 dep[u]、初始根（比如节点 1）下的距离和 f[1]；dfs2 用转移式 ans[v] = ans[u] + n - 2 * sz[v]（边权为 1 的简化版）推下去。
这个过程依赖两个强假设：
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 树结构固定
- 所有子树大小
sz[v]是准确且全局一致的
一旦你动了某条边或某个点权，sz[v] 就可能错，而 sz 错一点，ans[v] 就全错——因为每个后代节点的 ans 都叠着前面的误差。
所以：
- 单次修改后，必须重算受影响的子树
sz - 然后重跑从该子树根开始的换根传播链，不能只改一个点
哪些修改能 O(1) 或 O(log n) 更新？
取决于你存了什么、改了什么：
-
点权修改（不影响结构）：如果
ans[u]定义为 “以 u 为根时所有点的加权深度和”，且权重只在点上，那只要不涉及子树计数变化，有时可用额外数组（如sumW[u]表示子树权值和）配合换根式微调。但标准距离和问题里，点权不参与转移，这类修改通常不影响ans[]。 -
边权修改（比如把
u-v边权从 w 改成 w'）：影响的是整棵子树的深度偏移。你需要：- 判断哪边是子树（设
v在u的子树内），重新计算v子树内所有dep的 delta = (w' − w) - 然后按换根式反向推：对每个在
v子树中的节点x，其ans[x]变化量 = delta × (n − 2 * sz[x]) —— 这个公式来自原推导中“每少走 delta，子树内点贡献 −delta×sz[x]，子树外点贡献 +delta×(n−sz[x])”
- 判断哪边是子树（设
-
删边 / 加边（树变森林或重构）：换根DP彻底失效。
sz[]、连通性、父子关系全要重建。此时不如直接切树、重跑dfs1/dfs2，或换用 LCT / Euler Tour + 线段树等真正支持动态树的数据结构。
实际工程中怎么避免“重跑两遍 DFS”？
常见 trick 是：
- 把树固定成静态，把“修改”转成“查询新配置”：比如每次操作生成新树副本，预处理换根结果，用哈希或 ID 缓存结果（适合离线批量修改）
- 若只有少量修改（≤ 3 次），直接暴力重算——
O(n)对于n ≤ 2×10^5在现代 CPU 上不到 10ms，比写复杂维护逻辑更稳 - 用欧拉序 + 差分 + 树状数组维护子树 size 变化，但仅适用于「单点子树 size 增减」这种极受限场景；真实边权/结构变动无法靠它兜底
换根DP不是为动态设计的，它的快，建立在“只做两次遍历”的静态前提上。想让它响应修改，就得接受：要么限制修改类型，要么接受局部重算，要么换一套支持动态树的方案。最常被忽略的一点是——你以为改了一条边只影响两个点，其实它可能让半棵树的 sz 和 ans 全失效。
