简介如果处理“所有经过某一个顶点的链对答案的贡献”的时间复杂度为$O(n)$或者$O(nlogn)$，那么运用点分治的思想可以把问题规模降为$O(nlogn)$或$O(nlog^2n)$，而非暴力枚举顶点计算答案的$O(n^2)$。
阅读全文
MorphLing
10月 08, 2020
题目描述Compute 有一棵 n 个点，编号分别为 1∼n 的树，其中 s 号点为根。Compute 在树上养了很多松鼠，在第 i 个点上住了 ai个松鼠。
因为某些缘故，它们开始同时向根节点移动，但它们相当不安分，如果在同一个节点上，它们就会打起来，简单地来说以下事件会依序发生：
·如果一个节点上有 2 只或 2 只以上的松鼠，他们会打架，然后这个节点上松鼠的数量会减少 1；
·根节点的所有松鼠移动到地面，位于地面上的松鼠不会再打架；
·所有松鼠同时朝它们的父节点移动。
所有事件各自都在一瞬间完成，直至树上没有松鼠。
现在 Compute 想知道最终有多少只松鼠到达了地面。
阅读全文
MorphLing
5月 10, 2020