社区讨论
树剖的top不是一遍dfs就能求出吗?
学术版参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo91un6a
- 此快照首次捕获于
- 2023/10/28 04:12 2 年前
- 此快照最后确认于
- 2023/10/28 04:12 2 年前
RT,本蒟蒻想不通
CPPvoid 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 条回复,欢迎继续交流。
正在加载回复...