回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共4篇）

Infinite Tree 来自专栏

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

树状数组虚树 *****

2021-02-23

0 746

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数组，并按照字典序排序题解：参考博客题目标题就已经透露...

后缀数组 ***** 思维

2021-01-20

2 641

E2. Daleks' Invasion (medium)

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

最小生成树 ***** lca

2020-11-17

2 586

CodeForces - 609E Minimum spanning tree for each edge

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

最小生成树 ***** lca

2020-11-17

2 708