首页 > 血压游戏

四糸智乃

发表于 2020-04-18 17:06:32

本题解需要掌握dsu on tree和长链剖的相关知识。具体可以见我的博客 dsu on tree：https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 长链剖分：https://blog.nowcoder.n 展开全文

HgWalK

发表于 2020-04-18 21:33:46

中规中矩的虚树写法不难发现，只有同一深度的松鼠才会打架。那就easy了啊，把同一深度的所有点拎出来，建一棵虚树，合并一下，就好了。对于一个点，记表示到达该点的松鼠数量，那么其中表示在原树上的深度。这个方程应该很好理解吧（雾。然后每次把答案加上就好了(注意要满足先)。复杂度：瓶颈在求lca 展开全文

User_Does_Not_Exist

发表于 2020-04-18 17:34:57

Nowcodercontest5278G血压游戏做法非常多。。。比如对于同一层的点直接建立虚树，然后模拟dp即可如果不想建虚树，可以直接维护合并，每次合并得到的一定是同层点按照dfs序排序之后相邻两点的之一处理出所有这样的LCA，然后按照dep从大到小依次操作用一个set维护，每次取出子树展开全文

ShepherdsPurse

发表于 2020-04-21 01:55:06

来一个的做法：直接采用长链剖分，做到时间复杂度为, 不需要线段树之类的结构知识点:长链剖分长链剖用于解决：子树类与深度相关可合并的静态查询类问题，基础复杂度为流程：相对于重链剖分，相当于把size换成长度，重儿子也是长度最长的儿子性质性质一：所有链长度和是级别的这是因为所有点在且仅展开全文

s_r_f

发表于 2020-04-18 19:04:07

一颗个点的以为根的树树上有一些松鼠记点上的松鼠数目为进行若干次以下步骤直到所有都为对于所有令对于所有令 , (其中表示的儿子集合下同) 求最后的通过观察可以发现不同深度的点之间互不影响所以我们可以对于每种深度的点分别考虑建出虚树然后记为子展开全文

蒟蒻wjr

发表于 2020-04-20 11:41:32

需要掌握线段树合并的基本知识。显然只有同一深度的会合并，我们将每次合并后的线段树在头结点打一个递减标记、每次合并需要将其标记下传，最后在叶节点之间的合并中使用上这个函数，因为只有头结点统计答案，所以到头结点时标记全部下传即可。 #include <cstdio> #include & 展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛