最小生成树

必做题

1. 洛谷 P1194. 买礼物（虚拟源点）
2. AcWing 1146. 新的开始（虚拟源点）
3. AcWing 1143. 联络员
4. 洛谷 P1195. 口袋的天空
5. AcWing 1145. 北极通信网络
6. 洛谷 P2323. 公路修建问题
7. 洛谷 CF472D. 构造树
8. AcWing 346. 走廊泼水节
9. AcWing 347. 野餐规划
10. AcWing 349. 黑暗城堡（最短路径生成树）
11. 洛谷 P2121. 拆地毯（最大生成树）
12. 洛谷 P4208. 最小生成树计数
13. 洛谷 P4180. 次小生成树

选做题

1. 洛谷 P1265. 公路修建
2. 洛谷 P1191. 无线通信网
3. 洛谷 P1340. 兽径管理
4. 洛谷 P1537. Out of Hay S
5. 洛谷 P1396. 营救
6. 洛谷 P1550. Watering Hole G
7. 洛谷 P2700. 逐个击破
8. 洛谷 CF1245D. 电网
9. 洛谷 P3623. 免费道路
10. 洛谷 CF1120D. 能量树

树上问题

树的重心

1. AcWing 846. 树的重心
2. 洛谷 P1395. 会议
3. 洛谷 P1364. 医院设置
4. 洛谷 P5666. 树的重心

树的直径

1. AcWing 1072. 树的最长路径
2. AcWing 350. 巡逻
3. AcWing 351. 树网的核
4. AcWing 1075. 数字转换
5. 洛谷 P5536. 核心城市
6. 洛谷 P4408. 逃学的小孩

最近公共祖先

必做题

1. 洛谷 P3379. 最近公共祖先
2. AcWing 1172. 祖孙询问
3. AcWing 1171. 距离
4. 洛谷 P4281. 聚会
5. 树的直径
6. 洛谷 P4180. 次小生成树
7. 洛谷 P4556. 雨天的尾巴
8. 洛谷 P10930. 异象石
9. AcWing 357. 疫情控制

选做题

1. 洛谷 P2420. 让我们异或吧
2. 洛谷 P3884. 二叉树问题
3. 洛谷 P6374. 树上询问

树上前缀和与差分

前缀和

1. 洛谷 P4427. 求和

差分

1. 洛谷 P3128. Max Flow
2. AcWing 352. 闇の連鎖
3. 洛谷 P3258. 松鼠的新家
4. 洛谷 P2680. 运输计划

树链剖分

1. 洛谷 P2590. 树的统计
2. 洛谷 P3178. 树上操作
3. 洛谷 P3384. 树链剖分
4. 洛谷 P1505. 旅游

虚树

1. 洛谷 P2495. 消耗战
2. CF613D. Kingdom and its Cities

基环树

1. AcWing 358. 岛屿
2. AcWing 359. 创世纪

负环与差分约束

1. AcWing 940. 虫洞
2. AcWing 341. 观光奶牛
3. 洛谷 P1993. 小 K 的农场
4. 洛谷 P4926. 倍杀测量者
5. 洛谷 P3275. 糖果
6. AcWing 362. 区间

欧拉路

图的连通性

无向图的连通性

割点与桥

1. 洛谷 P3388. 割点
2. 洛谷 P1656. 炸铁路
3. AcWing 363. B 城

无向图的双连通分量

1. 洛谷 P2860. Redundant Paths
2. AcWing 364. 网络
3. 洛谷 P4630. 铁人两项
4. AcWing 365. 圆桌骑士

有向图的连通性

有向图的强连通分量

1. AcWing 367. 学校网络
2. AcWing 368. 银河
3. 洛谷 P2341. 受欢迎的牛

有向图的必经点与必经边

2-SAT 问题

二分图

1. 洛谷 P1525. 关押罪犯

二分图最大匹配

1. AcWing 372. 棋盘覆盖

二分图带权匹配

二分图最小点覆盖

二分图最大独立集

有向无环图的最小路径点覆盖