2020.5.2 ACM Google Cup 2011 Invitational Programming Contest prob:4/6/10 rank:11/69

树套树 ps:以前的一些链接搬运中，还有一个坑待填

最小生成树

拓扑排序

多项式对数函数

林星涵： 洛谷P4278 带插入区间K小值 树套树、块状链表模板，代码量较大，仅作练习代码能力食用。

陶吟翔：Codeforces597Div2-D，题目大意是有$n$个城市，现在要让每个城市都通上电，可以选择在若干个城市建造发电厂，在第$i$个城市建造发电厂需要花费$c_i$的钱，或者选择在两个城市之间连接电缆，在第$i$个城市和第$j$个城市之间连接电缆需要花费$(k_i+k_j) \times d$的钱，$d$为两个城市间的曼哈顿距离，最小化总花费。解法十分巧妙，首先在城市与城市之间建边，并且建立一个超级源点和每个城市连边，边权为在每个城市建造发电厂的花费。这样一来，我们对新图求最小生成树的值即可，这样可以保证至少有一个城市建造了发电厂，每个城市都通上电且花费最小。具体代码可以在最小生成树的专题里找到，这里是网址

郭衍培：洛谷1891 疯狂LCM 给定正整数n,求$\sum^n_{i=1}\text{lcm}(n,i)$。推式子，不难发现其实是要求$n\sum_{d|n}\sum^d_{i=1}i[\gcd(i,d)=1]$。值得注意的是，$\sum^d_{i=1}i[\gcd(i,d)=1]=\frac{\phi(d)}{2}d$。于是枚举d即可。