一发最优解祭（
Description
给定一棵树，节点 \(1\) 到 \(n\) 标号，\(q\) 个操作，你需要维护一个路径可重集合 \(P\)，操作一共三种：
- 向 \(P\) 集合加入 \(u\to v\)。
- 在 \(P\) 集合中删掉 \(u\to v\)（保证操作之前有加入，并且只删一个）。
- 查询 \(P\) 集合中所有元素路径的 \(d\) 邻域的交集是否为空集。一条路径 \(p\) 的 \(d\) 邻域定义为所有到 \(p\) 距离不超过 \(d\) 的点组成的点集。
Solution
考虑到难以求出所有路径的 \(d\) 邻域交集，因为这个集合大小是 \(O(n)\) 的，考虑一个最优决策点 \(v\) ，使得这个点尽量能被 \(P\) 中最多的路径邻域覆盖到。
设 \(low\) 为 \(P\) 的元素路径中两个端点的 \(lca\) 深度最大的点，\(q\) 为这条路径，下证取 \(v=father_{d}(low)\) （即 \(low\) 的 \(d\) 级祖先）时最优。即题目原命题成立当且仅当 \(v\) 在这个邻域交集中。
考虑 \(p\in P\)，分情况讨论：
首先如果 \(p\) 有点经过 \(v\)，那显然是可以取的。
若 \(lca_p\in subtree(v)\) ，即 \(p\) 路径的 \(lca\) 在 \(v\) 的子树中，由 \(low\) 的深度最大的性质，显然有 \(dis(v,lca_p)\le d\)。
若 \(lca_p\notin subtree(v)\)，则 \(q\) 和 \(p\) 必然不存在交集且 \(p\) 在 ，那此时决策点肯定尽量往上取，但是由于 \(low\) 的限制，\(v\) 的深度不能小于 \(dep_{low}-d\)，那 \(v\) 取 \(low\) 的 \(d\) 级祖先是最优的。
所以我们可以维护出 \(low\)（具体可以使用 set 维护集合 \(P\) 所有路径 \(p\) 的 \(lca\)），然后求出 \(v=father_d(low)\)，判断 \(v\) 是否合法。
由于上面证明了 \(p\in P\) 的 \(p\) 经过 \(v\) 或者在 \(v\) 的子树内都是合法的，那就考虑在 \(v\) 子树外的所有路径，它们到 \(v\) 的距离是否 \(\le d\)，仍然分类讨论，令 \(u=father_d(v)=father_{2d}(low)\)：
若有路径没有经过 \(u\) 的子树：说明这条路径在 \(u\) 的外部，那就不可能距离 \(v\le d\)，直接判掉即可。
若所有路径都经过了点 \(u\) 的子树：那么只需要任意路径的 \(lca\) 到 \(v\) 的最长距离不超过 \(d\) 即可。因为 \(v\) 经过子树的路径一定满足，并且其它的路径一定是 \(lca\) 到 \(v\) 的距离最短。可以画图理解。
而这个最长距离可以用动态求子树直径解决，求出子树内以 \(lca(p)(p\in P)\) 为端点的最长路径 \(i\to j\)，然后最长距离就是 \(\max\{dis(v,i),dis(v,j)\}\) 了。
判断是否所有路径都经过了某棵子树可以树上差分，对于一条路径 \(i\to j\)，在 \(dfn_i,dfn_j\) 处 \(+1\)，在 \(dfn_{lca(i,j)}\) 处 \(-1\)，查询 \(u\) 子树和即可知道有多少条路径经过了 \(u\) 的子树。
然后动态求直径可以用线段树。基于一个基本结论：一个连通块 \(A\) 合并到另外一个连通块 \(B\) 上，新的直径端点必然在 \(A\) 直径端点、\(B\) 直径端点 \(4\) 个中取 \(2\) 个，于是对于每一段连续的 \(dfn\) 区间维护区间直径端点即可。
代码很好写，不放了。使用树剖求 \(father_k\)，是 \(O(n\log^2 n)\) 的，但是如果换成欧拉序+ RMQ 的话可以达到 \(O(n\log n)\)。