山月记
给定 \(n\) 个点，\(m\) 条边的图 \(G\) 和他的一个生成树 \(T\)。图 \(G\) 可能有多个最小生成树。
询问是否存在一个点 \(x\) 使得 \(T\) 上所有以 \(x\) 为端点的路径 \(p\)，至少存在一个最小生成树包含 \(p\)。
一个重要观察：
在 Kruskal 的过程中，对于任意边集 \(E=\{e\}\)，不管处理顺序如何，最终得到的生成森林连通性相同。
证明
对于一种产生生成森林 \(G\) 的处理顺序 \(p\)，我们取其任意重排 \(p'\)，其产生生成森林 \(G'\)。
对于在 \(G\) 内最终连通的点 \(x_1,x_k\)，我们取出在 \(G\) 中连通 \(x_1,x_k\) 的路径 \(x_1\rightarrow x_2\rightarrow\cdots \rightarrow x_k\)。
假如边 \((x_1,x_2) \in G'\)，那么 \(x_1,x_2\) 在 \(G'\) 中连通。否则说明边 \((x_1,x_2)\) 加入时 \(x_1,x_2\) 已经连通。
同理可以说明 \(x_i,x_{i+1}\) 均连通，所以最终 \(x_1,x_k\) 在 \(G'\) 中同样连通。
所以在 \(G\) 中连通的点对 \(S=\{(x,y)\}\) 与在 \(G'\) 中连通的点对 \(S'=\{(x,y)\}\) 满足 \(S'\subseteq S\) 的关系。
同时，交换 \(p\) 与 \(p'\)，上述过程同样适用，所以有 \(S \subseteq S'\)。
因此可以推出 \(S=S'\)。
令 \(E\) 取边权 \(\le w\) 的所有边，可以得到一个推论：处理完所有边权 \(\le w\) 的边之后得到的生成森林 \(G_w\) 连通性相同。
这启发我们，不同权值的边实际上是独立的。因此我们可以分别考虑每一种权值的边。
假如我们想判断一条路径是否合法，对于每一种 \(w\)，我们找出路径上所有权值为 \(w\) 的边 \(E_w=\{e\}\)。
这条路径是合法的，实际上等价于 \(E_w\) 并上所有边权 \(\le w-1\) 的边的最小生成森林 \(G_{w-1}\) 后得到的图 \(G_w'\) 上无环。
假如对于每个 \(w\)，\(G_w'\) 无环都成立，可以通过将 \(E_w\) 内的边放到所有其他权值为 \(w\) 的边之前，由于权值相等，权值之和保持最小，同时 \(E_w\) 之内的边一定会被选入最小生成树中。
否则，取出 \(G_w'\) 中任意一个环，其上最晚被处理到的边必然权值为 \(w\)。在处理到这条边时其两端的点已经连通，其必然会被跳过。那么最终的最小生成树就不可能包含这条边。
于是我们现在为了检查路径是否合法，只需要维护 \(w\) 个并查集。其中的第 \(i\) 个初始时表示 \(G_{i-1}\) 的连通性。在其中加入权值为 \(i\) 的所有边，并维护环存在性即可。
更进一步地，为了检查点 \(x\) 是否是答案，可以从 \(x\) 开始深搜，改为使用可撤销并查集维护加/删边。
于是可以得到 \(O(n^2\log n)\) 的解法。
另外一个观察是：假如一条路径不合法，那么所有包含它的路径也不合法。
假如我们任取一个根 \(R\)，并依次检查它到每个儿子的子树内不合法路径的存在性。
假如 \(R\) 的一个儿子 \(r\) 的子树中某个点 \(r_0\) 满足路径 \(R\rightarrow r_0\) 不合法，那么答案只可能在 \(R\rightarrow r_0\) 的路径上。假如答案不在的话，一定存在某个从答案出发的路径完整包含 \(R\rightarrow r_0\) 这条路径，不合法。
这实际上允许我们通过点分治解决这个问题。
对于当前连通块，我们找出中心 \(R\)，并 \(O(n\log n)\) 地检查上述条件。如果不满足，答案只会在至多一个子树内，递归处理即可。
时间复杂度 \(O(n\log^2 n)\)。