社区讨论

树剖的top不是一遍dfs就能求出吗?

学术版参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo91un6a
此快照首次捕获于
2023/10/28 04:12
2 年前
此快照最后确认于
2023/10/28 04:12
2 年前
查看原帖
RT,本蒟蒻想不通
CPP
void dfs1(int u){
    soncnt[u] = 1;
    for (int i = hd[u]; i;i=e[i].nt){
        v = e[i].to;
        if(v==fa[u]){
            continue;
        }
        fa[v] = u;
        dep[v] = dep[u] + 1;
        dfs1(v);
        soncnt[u] += soncnt[v];
        if(soncnt[son[u]]<soncnt[v]){
            son[u] = v;
        }
        top[v] = v;
    }
    top[son[u]] = top[u];
}

回复

4 条回复,欢迎继续交流。

正在加载回复...