不懂就问
查看原帖
不懂就问
637788
kimi0705楼主2024/9/4 20:47

这份代码为什么能相对于普通 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
    }
}

2024/9/4 20:47
加载中...