E. Tree Queries
记录两种做法，思路均来自官解。
1
考虑换根。将所有查询按照 \(x\) 分类，对于每种查询，考虑将 \(x\) 作为整棵树的根，那么删点操作就变得特别简单了：
- 删点 \(u\) 不是 \(x\) 的祖先 \(\rightarrow\) 等价于删去 \(x\) 的整个子树
- 删点 \(u\) 是 \(x\) 的祖先 \(\rightarrow\) 等价于只留下 \(path(u, x)\) 上从 \(u\) 往下走的第一个点 \(v\) 为根的子树
很容易想到将子树看作区间，那么每次删点相当于删掉了某一个区间；假设共删 \(k\) 个区间，那么我们可以利用所有删除的区间去求所有未被删除的区间，数量同样是 \(O(k)\) 级别的。然后我们只需要在每个未被删除区间上查询结点深度最大值即可。
子树看作区间，即对原树作 \(dfn\) 序；区间查询即 RMQ。
那么我们现在就只需要考虑如何进行换根操作。我们要维护的仅是每个结点在换根后新的深度。显然，对于 \(u \rightarrow v\) 的换根操作（\(u\) 是 \(v\) 的父亲），我们只需要修改至多 \(3\) 个区间，因为深度变化无非就是：
- 以 \(v\) 为根的子树内的所有点的深度减 \(1\)
- 其他点的深度均加 \(1\)
因此只需要在 \(dfs\) 过程中换根维护新树的所有结点深度，然后处理每种查询的每个删点操作就行了。RMQ 显然需要用线段树。具体实现见代码。
code1
2
考虑树的直径。
一些前置知识：
- 在一棵树中，设直径为 \(path(u, v)\)，则对于 \(\forall x\)，\(path(x, u)\) 和 \(path(x, v)\) 其中一个一定是从 \(u\) 出发的最长路径。（结论1）
- 合并两棵树形成的新直径一定是在原来两棵树共 \(4\) 个直径端点中选其中 \(2\) 个作为一对新的路径端点，构成的 \(C_{4}^{2}\) 种方案之一。（结论2）
那么，对于每个查询，我们只需要维护好删点后 \(x\) 所在连通块的两个直径端点就行了。
而由解法 \(1\) 可知，操作后未被删除的所有连通块可以由 \(O(k)\) 个 \(dfn\) 序上的区间表示。我们只需要对于每个连通块查询对应区间上的两个直径端点就可以了。
而上述有关树直径的两个结论就派上用场了：我们可以用线段树维护 \(dfn\) 序上每个区间代表连通块的两个直径端点。由结论2，对于两个连通块的合并，枚举 \(6\) 种 四选二 ，并取其中相距最远的两个点作为合并后连通块的两个直径端点就行了。（即线段树的 pushup 函数），具体实现见代码。
每个连通块只需要在上述建好的线段树中查询某个区间。由结论1，每次查询只需要用 \(x\) 和 两个直径端点 之间的距离来更新答案。
code2
F. Beautiful Tree
待补。。。
code