tarjan缩点 发表于 2020-10-09 更新于 2023-08-02 分类于 oi ， 学习笔记 ， 图论 强连通定义：在有向图 G{V,E}G\{V,E\}G{V,E} 中，对于点集 V′∈VV'\in VV′∈V , 点集中的任意两点都可达，则称 V′V'V′ 为强连通。 阅读全文 »
换根dp 发表于 2020-10-09 更新于 2023-08-02 分类于 oi ， 学习笔记 ， dp 先看一个题目 CF161D Distance in Tree 考虑 dp（当然点分治也可以做），先求出 f(u,k)f(u,k)f(u,k) 表示将树中的 uuu 作为根节点后，深度为 kkk 的节点数量，则答案为 ∑u∈Gf(u,k)2\dfrac{\sum_{u\in G}f(u,k)}{2}2∑u∈Gf(u,k)。 阅读全文 »