一句话理解
父子关系是有根树的边的方向。
为什么要学
DP 转移、倍增 fa[k][u]。
讲解
存 fa[u]，有时也存儿子列表。换根 DP 会把父子角色对调。
例子
边 {u,v}，若 dep[u]<dep[v] 则 u 是父。
常见错误
- 深度没算就比父子。
- 森林里跨树比。
第 303 课
父子关系
🔵 基础 约 7 分钟
练习 做完再看下一课
深度更小的一端更靠近根，通常是父。
进度保存在本机浏览器里。
左右方向键也可翻课
第 303 课
父子关系是有根树的边的方向。
DP 转移、倍增 fa[k][u]。
存 fa[u]，有时也存儿子列表。换根 DP 会把父子角色对调。
边 {u,v}，若 dep[u]<dep[v] 则 u 是父。
深度更小的一端更靠近根，通常是父。
左右方向键也可翻课