Price List
可以发现答案只有三种：要么最短路乘\(a\)，要么最短路换成\(b\)，要么最短偶数路换成\(b\)。
这里的最短偶数路还要满足不经过\((x,y),(y,z)\)且\((x,z)\)有边。
前两种是平凡的，第三种考虑每次扩展两条边，这样是\(O(m^2)\)的。
不经过的是三元环，只有\(O(m\sqrt m)\)。考虑\((y,z)\)的边如果被经过了就没有必要再经过一次了所以可以删除，只有三元环的边会被重复遍历，时间复杂度\(O(m\sqrt m+n)\)
Triumphal arch
显然先二分变成判定性问题，然后对于某个\(k\)判断可行。
首先肯定要把\(1\)周围围满，然后直接考虑剩下的放哪里似乎有些棘手。
不妨从下往上考虑。设\(f_i\)表示子树内还有多少是需要放的，作为一个点\(x\)，肯定要把子树内尽量放满，因为哪边没放满往那边走就输了，因此\(f_u=\sum\limits_{(u,v)\in E}{f_v+1}\)。然后\(f_u=\max(0,f_u-k)\)，最后看\(f_1\)是否为\(0\)即可。
时间复杂度\(O(n\log n)\)
Tower Defense Game
首先请您回忆一下您最开始是怎么乱搞最小点覆盖的。
大概是随机一个点的顺序然后看每个点被覆盖了没有，如果没被覆盖了那么就覆盖。
然后这就是这道题做法。因为距离为\(2\)，所以无论放一条边哪个端点上都至少有原来距离为\(1\)的效果。
Polarization
什么玩意不同写法空间相差怎么这么大。
首先肯定是选定一个点，然后将它的子树一部分内向，一部分外向。
可以证明选重心最优，然后相当于要考虑一堆数选出一些和最接近一半。
直接bitset\(O(\frac{n^2}{w})\)不太能过，因为物品总和为\(n\)，所以只有\(O(\sqrt n)\)种物品，然后二进制拆分成\(O(\sqrt n\log n)\)个之后再bitset就可以做到\(O(\frac{n\sqrt n\log n}{w})\)了。
标签：一个点,log,submission,覆盖,POI2013,然后,sqrt From： https://www.cnblogs.com/275307894a/p/17010278.html