关于淀粉的一些疑惑

P3806 【模板】点分治 1

pikabi @ 2020-09-26 11:32:56

  • 在点分治的 getdis (查找距离) 中，如果没有判断 v ( 目标节点 ）是否 vis (以之为根过) 而只判断是否为父亲就会挂掉。

  • 但是在一棵点分治树中，我先找到当前根的儿子，再找到儿子的儿子，由于其不会走到父亲节点，也就根本不会走到 vis 过的节点，应该无所谓是否判断 vis 的，想问一下为什么不这样做会挂掉。

by pikabi @ 2020-09-26 11:34:26

也就是在

inline void get_dis(int p, int fa, int val){
    for(int i = head[p]; i; i = e[i].nxt){
        if(e[i].to == fa || vis[e[i].to ]) continue;
        res[++sum] = val + e[i].val ;
        get_dis(e[i].to , p, val + e[i].val );
    }
}

语句中 把

|| vis[e[i].to]

去掉挂的原因

by Prean @ 2020-09-26 11:53:47

因为那一部分不在这棵树里面啊

by 鏡音リン @ 2020-09-26 11:58:35

为啥不会走到vis过的点 你的分治中心是重心 可不是上一个分治中心的子节点

by pikabi @ 2020-09-26 12:03:07

@鏡音リン thx，简洁易懂

by TokyoFreshAir @ 2020-09-26 21:38:03

老EDG粉丝了

|