图论专题三

第三讲

（5分20秒开始有声音）

1. LCA拓展

2. 树的序列化

  2.1 dfs序——树上子树的查询和修改，需要结合线段树

  2.2 括号序列——求链上的和

3. 最小生成树

  3.1 prim算法

  3.2 kruskul算法

4. 次小生成树

  4.1 数据量10^3做法

  4.2 数据量10^5做法

  4.3 数据量10^6做法

5. PPT37页 problem4 CF733F Drivers Dissatisfaction

进阶指南上的题目：

1. 走廊泼水节

2. picnic planning（野餐规划 POJ1639）

3. 沙漠之王（最优比率生成树POJ2728）

4. 黑暗城堡