回归梦想的博客

Infinite Tree 来自专栏

Infinite Tree 题意：题解：参考博客看了好一阵子才明白。。。emm。我们先按照题意画出一部分树我们先不考虑复杂度，这题应该怎么做？题目给了每个点的权值w[i]，问一个点到所有的节点路径长度*点权之和最小是多少，很明显是树形dpdp[i]表示以i为根的子树到i的w和sum[i]表示乘...

B-Suffix Array

B-Suffix Array 题意：一个字符串只含有a和b，先给出b数组的构造方式：对于每个位置i来说：如果存在一个位置j，使得j<i,且s[j] == s[i],则b[i]=i-j 否则b[i]=0现在对字符串每个后缀都构造B数组，并按照字典序排序题解：参考博客题目标题就已经透露...

E2. Daleks' Invasion (medium)

题意：ｎ个点，ｍ个边，生成一个最小生成树，问对于不在最小生成树的边将其边权最大改为多少后，最小生成树可以包含该边输出ｍ－（ｎ－１）个答案如果ｎ＝＝ｍ－１的话，不需要输出任何东西题解：这个题和CodeForces - 609E 是完全一样的，就是输出不一样，换了问法，代码改改就能过题解链接对于不...

CodeForces - 609E Minimum spanning tree for each edge

题意：有个无向图，问在必选第i条边的情况下，最小生成树是多少？i会枚举每一个边题解：最小生成树好求，Kruskal即可我们记录最小生成树的值为len对于边(u,v),如果(u,v)是最小生成树的边，那直接输出答案len如果不是的话，我们就要去掉最小生成树中从u到v的路径上权值最大的边mlen，...