对每条非树边分别考虑。假设有一条非树边 $e=(u,v)$，对任意的点 $x$，$x$ 合法当且仅当 $f(u,x)\ge \min\{f(v,x),w_e\}$ 且 $f(v,x)\ge \min\{f(u,x),w_e\}$。其中 $f(u,v)$ 表示 $u$ 和 $v$ 在树上的路径的边权最小值。反之，$x$ 不合法当且仅当 $f(u,x)\ne f(v,x)$ 且 $\min\{f(u,x),f(v,x)\} < w_e$。

假设 $w_e\le f(u,v)$，则显然这条边没有影响。假设 $w_e >f(u,v)$，由于 $\min\{f(u,x),f(v,x)\}\le f(u,v)$，所以第二个条件一定满足，因此满足 $f(u,x)\ne f(v,x)$ 的所有点 $x$ 都不合法。

考虑加入树上边权 $> f(u,v)$ 的所有边，则满足上述条件的点即为 $u$ 和 $v$ 分别所在的连通块内的点。将它们标记成非法即可。

时间复杂度 $O((n+m)\log n)$。