这份代码为什么能相对于普通 dp 降低复杂度,什么思想
void dfs2(int u) {
if(son[u]) { // 如果当前节点 u 有重儿子
dfs2(son[u]); // 递归处理重儿子
swap(f[u], f[son[u]]); // 交换 f[u] 和 f[son[u]],以便重用重儿子的结果
f[u].push_back(1); // 在 f[u] 中添加一个 1,表示当前节点 u 自己
ans[u] = ans[son[u]]; // 初始化 ans[u] 为重儿子的答案
if(f[u][ans[u]] == 1) ans[u] = len[u]; // 如果 f[u][ans[u]] 为 1,则更新 ans[u] 为当前节点的长度
for(auto v: e[u]) { // 遍历当前节点 u 的所有邻居节点 v
if(v == fa[u] || v == son[u]) continue; // 跳过父节点和重儿子
dfs2(v); // 递归处理其他儿子
for(int i = len[v]; i >= 0; i--) { // 遍历子树 v 的所有深度
int tmp = i + len[u] - len[v] - 1; // 计算在 f[u] 中对应的位置
f[u][tmp] += f[v][i]; // 将 f[v][i] 的值加到 f[u][tmp] 中
if(f[u][tmp] > f[u][ans[u]] || (f[u][tmp] == f[u][ans[u]] && tmp > ans[u])) {
ans[u] = tmp; // 更新 ans[u] 为 tmp,如果 f[u][tmp] 更大或相等但 tmp 更大
}
}
}
} else { // 如果当前节点 u 没有重儿子
f[u].push_back(1); // 在 f[u] 中添加一个 1,表示当前节点 u 自己
ans[u] = 0; // 初始化 ans[u] 为 0
}
}