- P2860 [USACO06JAN] Redundant Paths G
先转化为加尽量少的边使得图为边双。 注意到边双具有传递性，则先进行缩点。(此处注意tot=1和lst^1的实现细节)
则问题又转化为加尽可能少的边，使一个全是割点的图变成边双。
边加在叶子上较优，在两个叶子之间加边等同于用两者之间的路径覆盖树。
用一条边连接两个叶子，最终连上所有叶子，可以等价转化为用尽可能的链覆盖整棵树。
经典结论：最小链数为 T 的叶子个数除以 2 上取整。 证明考虑先全部连上再对局面进行调整(典)，奇数个叶子先将多出来的连到 deg≥3 的节点上。对于每条没被覆盖的边，隔开的两个连通块分别取配对的两个叶子交换覆盖(不可能只有一个叶子，因为其已经配对，肯定会穿过当前边)，一定可以覆盖原有+当前边，更优。 - P2916 [USACO08NOV] Cheering up the Cow G
如果觉得某种方式可能不够优，记得可以重新赋边权(点权)再最优化处理。
注意到每个点代价次数即为度数（欧拉序中一个点出现的次数也为其权值），则把点权扔到边上处理。
然后最小生成树。 - P3623 [APIO2008] 免费道路
首先考虑没有任何限制，求生成树，每条边都是等价的。
如果只在鹅卵石路中选有贡献的k条边连上，可能会出现剩下边怎么连都无法连通，但实际有解的情况。因此先把非鹅卵石路都连上，把必选的鹅卵石路选出来，然后清空重新连，随便选有贡献的就好了。注意判断无解。
Shortest Path
- CF1887B Time Travel
别的都比较常规。跑dij的时候边权动态，显然如果要等的话等到时间最近的那个最优，对于每条边记录下属于的边集，对于每个边集记录有效时间，然后upper_bound一下即可。（返回迭代器的话end解引用是最后一个 注意特判）
Tree
- CF1805E There Should Be a Lot of Maximums
- 一条边分成的两个子树\(\rightarrow\)放在dfs序上拍平，一个区间，一个前缀；复制一遍，两个区间，然后转化成了求区间出现次数不小于2的最大数字的ds，此处2取任意常数都能做，具有普适性。
- 考虑这个2的性质，对每条边有关点求答案\(\rightarrow\)考虑每个点对哪些边有什么贡献，记一个权值出现次数为cnt，若\(cnt > 2\)，根据鸽巢原理，随便怎么分都有一棵子树可被记入；若\(cnt = 2\)，只有在出现的两个点之间的路径上不能被记入，剩下的都行；若\(cnt = 1\)，无论如何都无法被记入。对于树上路径直接上树剖，求得路径的补集即可。code
- CF1805D A Wide, Wide Graph 考虑优化每个点合并的次数，比较容易想到仅保留最远一次合并。如何证明？经典结论：离树上某个点最远的点在树直径的两个端点中，如果我们考虑这样求出最远点，一开始会先连上直径，然后所有都和直径端点合并，只会向一个大连通块合并，正确性显然。问题在于我场上写了换根dp实现求最远点，这个证明考虑对于点u，在直径端点中和s较远，我们的决策选中了v成为u的最远点，和u到s距离相等，这说明t和v同样构成合法直径，t,v,s一开始就连上了，所以依旧仅有一个大连通块(附加结论，u,v一定经过直径s,t，应该是对的)。code