树相关的进阶概念和算法
Login to join training plan
- 树的直径、重心等概念的应用；
- LCA模板，请老老实实用多种做法解决；
- DFS序的应用（主要习题在LOJ），树上差分；
- 树链剖分。
Section 1. 进阶概念
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P253 【模板】树的直径 | 39 | 10 | 7 |
| P5536 【XR-3】核心城市 | 48 | 7 | 8 |
| P1099 [NOIP2007 提高组] 树网的核 | 13 | 2 | 9 |
| P2195 HXY造公园 | 0 | 0 | (None) |
| P1395 会议 | 13 | 9 | 7 |
Section 2. LCA与树上差分
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3379 【模板】最近公共祖先（LCA） | 132 | 16 | 8 |
| P132 「一本通 4.4 例 1」点的距离 | 11 | 8 | 8 |
| P5002 专心OI - 找祖先 | 8 | 2 | 10 |
| P3128 [USACO15DEC] Max Flow P | 13 | 6 | 8 |
| P3258 [JLOI2014] 松鼠的新家 | 19 | 7 | 7 |
| P8972 『GROI-R1』 一切都已过去 | 0 | 0 | (None) |
Section 3. 树链剖分
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3384 【模板】重链剖分/树链剖分 | 33 | 7 | 8 |
| P3379 【模板】最近公共祖先（LCA） | 132 | 16 | 8 |
| P3178 [HAOI2015] 树上操作 | 7 | 4 | 10 |
| P4315 月下“毛景树” | 0 | 0 | (None) |
| P1505 [国家集训队] 旅游 | 4 | 0 | 10 |
| P2486 [SDOI2011] 染色 | 0 | 0 | (None) |
| P3976 [TJOI2015] 旅游 | 0 | 0 | (None) |
| P3313 [SDOI2014] 旅行 | 0 | 0 | (None) |
| P4211 [LNOI2014] LCA | 0 | 0 | (None) |
