已知有 nnn 个点,mmm 条边的无向连通图。第 iii 条边记作 (ui,vi)(u_i, v_i)(ui,vi)。设 f(i)f(i)f(i) 表示最大的 jjj,使得 (uj,vj)(u_j, v_j)(uj,vj) 到 (ui−1,vi−1)(u_{i - 1}, v_{i - 1})(ui−1,vi−1) 构成的子图中 uiu_iui 与 viv_ivi 在同一联通快中(若不存在则为 111),求证:∑i=1m(i−f(i)+1)\sum\limits_{i = 1}^m (i - f(i) + 1)i=1∑m(i−f(i)+1) 在 O(nm)O(nm)O(nm) 级别。
thx!