树剖的top不是一遍dfs就能求出吗?
  • 板块学术版
  • 楼主PeyNiKge
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/4/9 14:33
  • 上次更新2023/10/28 04:12:06
查看原帖
树剖的top不是一遍dfs就能求出吗?
372219
PeyNiKge楼主2022/4/9 14:33

RT,本蒟蒻想不通

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];
}
2022/4/9 14:33
加载中...