下面是我为你整理的一份非常实用的 🧠 「换根 DP 模板小抄」，专为比赛/考试场景设计，结构清晰，覆盖常见题型和套路。

📋 换根 DP 模板小抄（建议收藏）

✅ 一、基本术语约定（通用变量）

sum[u]   // 当前以 u 为根的总代价（可加权距离和）
size[u]  // u 子树的权重和（例如：人口数 / 点权 / 子树大小）
total    // 整棵树的总权重（如总人口，总点权）

✅ 二、通用换根转移公式

从节点 u 移动到其子节点 v：

$$ \text{sum}[v] = \text{sum}[u] + \text{total} - 2 \times \text{size}[v] $$

🧠 理解公式含义：

  • v 的子树内的人更近了（距离 -1，总代价减少 size[v]）
  • 其他点更远了（距离 +1，总代价增加 total - size[v]）

✅ 三、基本流程模板

void dfs1(int u, int fa) {size[u] = weight[u];  // 初始化自身权重for (int v : G[u]) {if (v == fa) continue;dfs1(v, u);size[u] += size[v];sum[u] += sum[v] + size[v]; // 所有下属多走1步}
}void dfs2(int u, int fa) {for (int v : G[u]) {if (v == fa) continue;sum[v] = sum[u] + total - 2 * size[v];dfs2(v, u);}
}

✅ 四、常见换根 DP 应用题型汇总

题型 状态定义 备注
📍 树上建医院 sum[u] = 所有点到 u 的人口加权距离 本题即
🎯 树的重心 max_subtree[u] 表示最大子树大小 换根用“最大值转移”
📦 所有点到根的路径和 sum[u] = 所有点到 u 的距离和 纯路径和时，size=1
📈 子树点权和统计 sum[u] = 所有子树点权和 可换根统计每点为根时子树总权重
🧮 树上贡献和（如颜色、路径数） sum[u] = 所有路径或组合贡献 树形乘法常结合换根做

✅ 五、注意事项与易错点

错误点 正确做法
✅ 忘记更新 size[v] size[u] += size[v] 放在 dfs1 中
✅ sum[v] 推导错 用 sum[v] = sum[u] + total - 2 * size[v]
✅ 父子边访问重复 if (v == fa) continue; 保证树结构遍历
✅ 没初始化 h[], idx 向前星时务必 memset(h, -1, sizeof h)，idx = 0

📚 额外建议：比赛前 3 套必练模板题

题名 平台 说明
树上建医院 蓝桥杯/洛谷 P1122 人口加权路径和最小
树的重心 蓝桥杯 / AcWing 846 换根统计最大子树大小
换根路径和 洛谷 P1352 没有上司的舞会 树形结构价值分配

🎁 附加（建议背熟的口诀）：

“换根更新 sum，total 不动摇；减去子树 size，加上其余逃。”