求助,实在想不明白
  • 板块学术版
  • 楼主Chinshyo
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/10/10 23:25
  • 上次更新2023/11/2 14:33:05
查看原帖
求助,实在想不明白
312820
Chinshyo楼主2023/10/10 23:25

差分还原的时候为什么上面这种判重是错的,下面就是对的

// void dfs(int x, int &ans) {
//     if(vis[x]) return;
//     val[x] = diff[x];
//     vis[x] = true;
//     for(int i = head[x]; i; i = edge[i].next) {
//         int y = edge[i].to;
//         dfs(y, ans);
//         val[x] += val[y];
//     }
//     ans = max(ans, val[x]);
// }
void dfs(int x, int fa, int &ans) {
    for(int i = head[x]; i; i = edge[i].next) {
        int y = edge[i].to;
        if(y == fa) continue;
        dfs(y, x, ans);
        diff[x] += diff[y];
    }
    ans = max(ans, diff[x]);
}

2023/10/10 23:25
加载中...