本题解需要掌握dsu on tree和长链剖的相关知识。
具体可以见我的博客
dsu on tree：https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98
长链剖分：https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9
题意：给你一棵树，重复做以下动作直到树上所有点的权值都为0
1、对于所有权值大于1的节点，权值减少1。当权值为1或者0时保持不变。
2、将根节点的权值累加计入答案ans。
3、在所有节点的权值变动之后，令所有节点的权值变更为它所有孩子节点的权值和（叶子节点变为0）。
首先因为，初始输入的权值和-减少的松鼠数目=答案ans。
那么实际上只要计算“减少的松鼠数目”也就能求出答案了。
减少的松鼠数目=
假设一开始节点的权值都是INF,那这个问题就变得很简单，它就是
，也就是节点i的最大深度。
那现在问题就是权值不是INF它怎么计算嘛，计算方法是类似的。
首先先尝试计算出根节点（1号节点）处减少的松鼠数目
那我想的是，反正松鼠不管在什么位置，反正最终都是要移动到根节点的。那么我在计算根节点处减少的松鼠数目时树结构其实就没什么用了，因为我只想知道每一层的松鼠到达根的时候，在根节点合并的松鼠数目。
那么我就知道，共同到达第一层的有2只松鼠，共同到达第二层的有2只松鼠，第三层有1只，第四层有4只。
然后因为到这个点的时候如果大于等于2只松鼠就要减少一只，所以在根处减少了3只松鼠。
然后发现算出来不对。
因为仅仅是一开始第四层（8号节点）的权值为4，当它真正移动到根节点的时候权值是发生变化的，那我就不知道它到根的时候的真实权值是多少。
那问题不大，起码思路是对的，只不过要想办法把这个“真实权值”给算出来。
怎么算呢？诶，我从叶子开始算不就好了。
计算叶子节点处减少的权值时，实际上就是如果叶子的权值>1，贡献就是1，否则为0。
在计算完成后，既然我都知道它在这里减少了1，那实际上就是少了一只松鼠啊，那么“真实权值”不就求出来了。
现在就可以计算第三层（7号节点）的权值了，以7号节点为根的子树每一层的“真实权值”之和分别为1,3。
所以在这里他也减少了1，并且我还知道它是在哪里减的，那么就真的给它减1就好。
以此类推...在计算完除根节点以外的贡献之后，最终在计算根节点时，也就同时求出了每一层到达根节点时的“真实权值”。
现在是真正的，同时到达第1,2,3,4层的松鼠数目分别为2,1,1,1。
所以在根节点处真正减少的松鼠数目为：1只。
好了，现在算法有了，如何实现？每次暴力for深度数组是)
的。
我们要做的事情实际上就是一个“维护子树深度相关的求值类问题”。
更何况它没有修改。
给你一个数组，支持以下三个操作：
1、查询数组L~R区间内大于1的数字的个数。
2、修改数组L~R区间内大于1的数字，让它们减少1。
3、给一个单点加上一个数字
那这个题太裸了，就是带暴力成分的线段树。同时维护一个区间最小值，如果区间的最小值+lazy标记后发生了从非01数到01数的转化，就暴力重建线段树。
因为只能往下减，而往上加数是单点加的，所以仅会进行(n+操作3的操作次数)次的暴力重构。
所以线段树三个操作的均摊代价为)
（操作1,3为稳定复杂度，操作2均摊复杂度）
长链剖的基础复杂度为)
，里面套一个线段树后总复杂度为)
。
具体可以见我的博客
dsu on tree：https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98
长链剖分：https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9
一开始就读了个假题，读成了。“统计每一层的节点数目，然后输出和为奇数的层共有几层”这个题意，然后样例都过不去一脸懵逼。
1、对于所有权值大于1的节点，权值减少1。当权值为1或者0时保持不变。
2、将根节点的权值累加计入答案ans。
3、在所有节点的权值变动之后，令所有节点的权值变更为它所有孩子节点的权值和（叶子节点变为0）。
首先因为，初始输入的权值和-减少的松鼠数目=答案ans。
那么实际上只要计算“减少的松鼠数目”也就能求出答案了。
减少的松鼠数目=
假设一开始节点的权值都是INF,那这个问题就变得很简单，它就是
那现在问题就是权值不是INF它怎么计算嘛，计算方法是类似的。
先给一个样例
8 1 2 2 0 0 0 0 1 4 1 2 1 3 1 4 2 5 2 6 7 3 8 7
首先先尝试计算出根节点（1号节点）处减少的松鼠数目
那我想的是，反正松鼠不管在什么位置，反正最终都是要移动到根节点的。那么我在计算根节点处减少的松鼠数目时树结构其实就没什么用了，因为我只想知道每一层的松鼠到达根的时候，在根节点合并的松鼠数目。
那么我就知道，共同到达第一层的有2只松鼠，共同到达第二层的有2只松鼠，第三层有1只，第四层有4只。
然后因为到这个点的时候如果大于等于2只松鼠就要减少一只，所以在根处减少了3只松鼠。
然后发现算出来不对。
因为仅仅是一开始第四层（8号节点）的权值为4，当它真正移动到根节点的时候权值是发生变化的，那我就不知道它到根的时候的真实权值是多少。
那问题不大，起码思路是对的，只不过要想办法把这个“真实权值”给算出来。
怎么算呢？诶，我从叶子开始算不就好了。
在计算完成后，既然我都知道它在这里减少了1，那实际上就是少了一只松鼠啊，那么“真实权值”不就求出来了。
现在就可以计算第三层（7号节点）的权值了，以7号节点为根的子树每一层的“真实权值”之和分别为1,3。
所以在这里他也减少了1，并且我还知道它是在哪里减的，那么就真的给它减1就好。
以此类推...在计算完除根节点以外的贡献之后，最终在计算根节点时，也就同时求出了每一层到达根节点时的“真实权值”。
现在是真正的，同时到达第1,2,3,4层的松鼠数目分别为2,1,1,1。
所以在根节点处真正减少的松鼠数目为：1只。
好了，现在算法有了，如何实现？每次暴力for深度数组是
我们要做的事情实际上就是一个“维护子树深度相关的求值类问题”。
更何况它没有修改。
那指向性很明显，就是长链剖。
线段树部分
长链剖出来，相当于把问题转化到单链上面，也就是将问题转化成了：给你一个数组，支持以下三个操作：
1、查询数组L~R区间内大于1的数字的个数。
2、修改数组L~R区间内大于1的数字，让它们减少1。
3、给一个单点加上一个数字
那这个题太裸了，就是带暴力成分的线段树。同时维护一个区间最小值，如果区间的最小值+lazy标记后发生了从非01数到01数的转化，就暴力重建线段树。
因为只能往下减，而往上加数是单点加的，所以仅会进行(n+操作3的操作次数)次的暴力重构。
所以线段树三个操作的均摊代价为
长链剖的基础复杂度为
那么这个题就写完了。
京公网安备 11010502036488号