一行超人

发现最近写博客好随意啊，想怎么写怎么写

求miu函数以及fai函数的前缀和

BZOJ3944sum

 我看的是这里的题解：Gromah  Li Zhuohan  

不得不说这种变换实在太科幻了。。。

复杂度估计什么的不会证明。。。用hash应该是O（n^2/3），然后加了个map就成了O（n^11/12）了。。。但是两实测跑起来一样快。。。

爆int调了我3h最后在Gromah的help下才AC了 Orz

BZOJ3930: [CQOI2015]选数

先推莫比乌斯反演，然后发现我们需要知道miu函数的前缀和，而范围是1e9.。。预处理显然就挂掉了。那么我们的O（n^2/3）大法就派上用场啦！

虽然整个复杂度看起来很不靠谱的样子，但是还是1s跑过了

斯坦纳树

求一张图中使得给定点集连通的最小代价。点集的大小很小，一般都<=10.

然后dp[i][j]表示在i点点集连通状态为j的最小花费，那么有dp方程组：

dp[i][j]=min(dp[i][j],dp[i][k]+dp[i][j-k])其中k是j的一个子集。

dp[i][j]=min(dp[i][j],dp[k][j]+w[k][i]）其中k与i相邻，w[k][i]表示k到i的代价。

然后我们枚举j，先用子集更新ans。然后再在整张图上跑spfa来更新每个点的j状态的最优值。

其实我并不了解正确性

最后的最优解一定是一棵树的形态，而它的任何一部分也是一棵树的形态。

我们按论文上的来理解，dp[i][j]表示这棵树的根为i，然后连通的点集为j的最小代价。

考虑两种转移，第二种就是将这个根向上拓展（向下显然不优）

第一种就是合并两颗有根树。什么？你说重复的？我们自然可以把有重复的归到一个点集，然后用不重复的来得到更优的答案。

然后逐渐得到我们的最优解。好像很有道理的样子。。。原谅我是蒟蒻

BZOJ2595: [Wc2008]游览计划 

那么这题就是裸的斯坦纳树了。当然代码很好写。理解的不是太清楚总感觉怪怪的QAQ

BZOJ3205: [Apio2013]机器人

这题也是可以斯坦纳树搞的。

我比较二没想到DP方程QAQ

设dp[i][j][l][r]表示处在（i，j）使l-r合并的最小代价。那么有dp方程组

dp[i][j][l][r]=min(dp[i][j][l][r],dp[i][j][l][k]+dp[i][j][k+1][r]) 类似于上面的枚举子集

dp[i][j][l][r]=min(dp[i][j][l][r],dp[i'][j'][l][r]+1)其中(i',j')一步可以走到（i，j）

然后后面这一部分就spfa做。。。

UPD：其实我觉得这个不能叫斯坦纳树233 只是在列出dp方程之后采用了与斯坦纳树一样的处理方式。

然后就TLE了！

PoPoQQQ大爷教导我们

维护两个队列，将初始所有的点按照距离排序后从小到大加入队列1

但是我还是T了。拿来数据一测，我和PoPoQQQ都T了5个点。交上去，他A了，我T了。

自己没亲手AC真是太不爽了