题意：
有一棵树，这棵树上有很多果子，一开始每个果子都在，给出下面两种操作：
1.C x，改变果子x的状态，如果有，那么久摘下来；没有，就变为有；
2.Q x，问在x上面的（包括x）有多少个果子。
思路：
多叉树，朴素的更新方法就是从叶子到根的路径上的点的值全部更新，但是这样每更新的复杂度是O(n)。
所以就要考虑如何较快地更新。
树状数组的更新是logn，那么就要考虑如何把树上的问题转换为区间的问题，这就用到了dfs序。
“一棵子树的dfs序就变成了一个区间”
通过记录dfs序，那么一个节点及其子节点就构成了一段连续的区间，所以就可以用树状数组进行信息的维护。
对于这道题来说，对于每一个节点，记录两个信息，一个是第一次访问到它的时间l，第二个是它的子节点中最大的访问时间r，那么从l到r这一段连续的数字就是这个节点及其所有子节点的区间。
更新x，就是将l[x] ~ n这一段区间更新；
查询x上面的数字之和，就是查询1 ～ r[x] 与 1 ～ l[x]-1的差值。
这两个操作就是树状数组的基本功能，单点更新与区间查询。
注意建树不能用vector，得用链式前向星。
代码：
Original: https://www.cnblogs.com/kickit/p/9077354.html
Author: qrfkickit
Title: poj 3321 Apple Tree
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604631/
转载文章受原作者版权保护。转载请注明原作者出处！