Day 1
T1 找寻者
- 启示：
- 直觉？虽然边之间存在影响，但是边的贡献仍然是独立的：\(\sum_{e=(u,v)}siz_v\times P(T\mid e \texttt{ is light edge})\)。
- 快速判断问题强于什么？背包是不可避免的。
- 对于复杂度的精细分析？\(\sum_{u} (siz_{fa}-siz_u)\times siz_u\) 等价于所有点对在 LCA 处统计，是 \(O(n^2)\) 的。
T2 摩卡串
T3 夜空
T1 找寻者
T2 摩卡串
T3 夜空