子树内外合并
距离≤k 点权和
本课摘要
子树内外合并课程回答“子树内外贡献如何在第二遍 DFS 中合并”。内容以距离≤k 点权和为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。
- 判断子树内外合并的适用条件与状态边界
- 围绕“距离≤k 点权和”推导转移与计算顺序
- 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节
正在整理目录…
每个点的答案 = 子树内 + 子树外
前两节的距离和，换根系数是一句 就搞定的标量。但很多换根题的「答案」是一个更复杂的东西—— 比如 「距离不超过 的点权和」，它天然分成两截：
固定一个根后，任一点 的答案 = 子树内贡献 （ 往下的部分） + 子树外贡献 （ 经父亲往「树的其余部分」的那截）。 子树内的一截，第一遍后序就能直接算；难点全在子树外那一截怎么 补上。
父贡献减去「自己那一份」：换根的核心操作
换根到孩子 时，它的「子树外」 要从父亲 借。 但不能直接把 的全部信息给 ——因为 的信息里，有一部分正是「朝着 这棵子树」的， 对 来说那属于「子树内」，会重复计算。
核心操作就一句话：
父方向给 的贡献 = （父 的完整信息） − （朝 子树的那一份）
以「距离分层点权和」（子树内距 恰为 的点权和）为例，换根 分三步：
① 扣重复：父 距 的层里，混进了「从 走到 再拐回 子树、距 」的点，即 ；先减掉。
② 合并下推：此刻的 已是「 看出去的父方向」，把它的 层加到 ——父方向的点距 要多走一步。
③ 复原：把 ① 减掉的加回去，让 恢复成「完整的 」，供 的其它孩子换根时继续用。
本质
子树内外合并型换根，把 「父的完整信息」减去「本孩子子树贡献」 得到父方向，再合并进孩子—— 这就是「 由 回推」的一般套路。第一遍备好子树内，第二遍用「减一份、加一层、复原」把子树外沿边传下去。
跟着算一遍
用距离和把「内 + 外」看清楚（它是分层点权和最简的一维版）。链 ，无权，固定根 1：
看「内 + 外」怎么拼出答案
多一维状态：距离分层
「距离 的点权和」比标量距离和多一维： 记录子树内距 恰为 的点权和（ 从 到 ）。 第一遍合并子树：（子树 里距 为 的点，距 就是 ）。
换根时对每一层 都做一次「减一份、加一层、复原」。最终点 的答案 = 。 复杂度 ——每条边换根时扫 层。
易错点
换根三步的顺序与循环方向是关键：扣重复用 ，下推用 ，两处下标错位不同； 且「合并下推」会改到 ，务必先扣父、再推子、最后复原父，否则同一个父的多个孩子会互相污染。 分层数组第二维只需开到 （本题 ）。
例题
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
int n, k;
vector<int> g[N];
long long val[N]; // 点权
long long dp[N][21]; // dp[u][j]：只在 u 子树内，距 u 恰为 j 的点权和
// 第一遍：子树内的分层点权和（后序）
void dfs1(int u, int fa)
{
dp[u][0] = val[u];
for (int v : g[u])
{
if (v == fa) continue;
dfs1(v, u);
for (int j = 1; j <= k; j++)
dp[u][j] += dp[v][j - 1]; // 子树 v 里距 v 为 j-1 的点，距 u 就是 j
}
}
// 第二遍：换根，把『父方向』的分层点权补进来（前序）
void dfs2(int u, int fa)
{
for (int v : g[u])
{
if (v == fa) continue;
// ★先扣除重复：父 u 距 j-2 的层里，含了『经 v 又回来』的 dp[v][j-2]
for (int j = k; j >= 2; j--)
dp[u][j] -= dp[v][j - 2]; // 撤销自身子树对父这一层的贡献
for (int j = 1; j <= k; j++)
dp[v][j] += dp[u][j - 1]; // 再把父方向（此刻的 dp[u]）下推给 v
// 复原 dp[u]，供 u 的其它孩子换根时仍是『完整的 u』
for (int j = 2; j <= k; j++)
dp[u][j] += dp[v][j - 2];
dfs2(v, u);
}
}
int main()
{
cin >> n >> k;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i++) cin >> val[i];
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++)
{
long long s = 0;
for (int j = 0; j <= k; j++) s += dp[i][j]; // 距 i 不超过 k 的点权和
cout << s << endl;
}
return 0;
}