题目描述
长期以来，中心市的水没有什么问题。城市的下水道系统是一种有根树结构：中央水库位于树的根节点，房屋位于树的叶节点。水从中央水库通过管道延树边流向每间房屋，所有房屋都可以使用到水。
突然，强盗们占领了一些房屋。作为市长，你非常忧虑并且想要驱逐这些强盗。所以，你打算停止向那些强盗占领的房屋供水。为此，你可能需要阻断下水道系统的某些管道。如果从水库到某房屋的路径中至少有一条被阻断的管道，那么该房屋将无法取水。 你非常害怕强盗，所以你决定阻断最小数量的管道以免发生意外。同时，你关心居民，因此对于已确定数量的被阻断的管道，你希望最大限度减少没有强盗且无法取水的房屋的数量。
不幸的是，强盗们可能出现或消失在某些房屋里。所以在每次强盗位置改变后，你要询问科学家被阻断管道的最小数量和没有强盗且无法取水的房屋的最小数量。
输入格式
第一行的输入包含两个整数 \(n\) 和 \(q\)，下水道系统中节点的数量和强盗位置改变的次数 \((2\le n \le 10^5;1\le q \le 10^5)\)。
第二行包含对下水道系统的描述：一个有 \(n-1\) 个整数的序列 \(p_2,p_3,\dots,p_n\)，其中 \(p_i\) 表示节点 \(i\) 的父节点 \((1\le p_i < i)\)。中央水库位于 \(1\) 号节点。
接下来 \(q\) 行表示强盗位置的变化。每次改变为下面两种方式之一：\(“+\ v”\) — 强盗占领了位于节点 \(v\) 的房屋；\(“-\ v”\) — 强盗离开了位于节点 \(v\) 的房屋。
一开始，所有房屋都没有强盗。所有更改以正确的顺序进行：强盗不能占领它们已经占领的房屋，并且不能离开它们尚未占领的房屋。
输出格式
输出应包含 \(2q\) 个整数，每行有两个：\(c_i\) — 被阻断的管道的最小数量以及 \(h_i\) — 在阻断 \(c_i\) 个管道的情况下没有强盗且无法取水的房屋的最小数量。
题解
首先考虑最优化被阻断的管道个数，我们将叶节点按照所属 \(1\) 子节点的子树分组，对于分别位于两组的一对占领节点，我们无法找到一条管道阻断后使这两个节点同时不可达，而对于存在占领节点的一组而言，设占领节点构成的集合为 \(S\)，我们总能找到一条管道切断根节点到 \(S\) 的路径，具体的，这条管道就是 \(\operatorname{LCA}(S)\) 到根节点路径上任意一条边。综上，\(c\) 的值即为 \(1\) 子节点含有被占领节点的子树个数。
之后最优化没有强盗且无法取水的房屋的最小数量。根据上述分析，每组相互独立，\(h\) 为选择阻断的边 \((p_x,\ x)\) 中 \(x\) 内叶节点的个数减去该组占领节点的个数，\(x\) 取值为 \(\operatorname{LCA}(S)\) 到根节点（不含根节点）的路径上的任意一点，\(x\) 深度越浅，叶节点的个数就越多，因此 \(x\) 取 \(\operatorname{LCA}(S)\) 最优。
所以我们将问题转化为求 \(\operatorname{LCA}(S)\)。我们对树进行从 \(1\) 节点开始的 DFS，记 \(x\) 的 DFS 序为 \(dfn_x\)。存在下述性质：
\[ dfn_x=\min_{v\in S}dfn_v,dfn_y=\max_{v\in S}dfn_v\Rightarrow \operatorname{LCA}(S)=\operatorname{LCA}(x,y) \]
证明：假设存在 \(z\) 满足 \(dfn_z\in(dfn_x,dfn_y)\) 使得 \(\operatorname{LCA}(x,y)\) 不是 \(z\) 的祖先，那么在 DFS 进行对 \(\operatorname{LCA}(x,y)\) 的子树遍历时就不会访问到节点 \(z\)，所以 \(dfn_z\notin(dfn_x,dfn_y)\)，与假设矛盾，所以上述性质成立。
因此我们需要找到一个支持加入和删除，查询最值得数据结构。使用堆或平衡树即可在单次修改 \(O(\log n)\) 得时间内维护。而 \(\operatorname{LCA}\) 的计算，我们可以使用倍增，树链剖分，欧拉序等轻松得出。标程的复杂度为 \(O((n+q)\log n)\)。