T340658 战神

“厕所，拱门，机房”是乱斗的三个术语。厕所指规避同学和老师，最普遍的正常斗法。拱门指出乎同学和老师意料的精妙斗法。而机房则指最容易想到，但从长远来看最容易暴露的斗法。对于初斗者而言，通常从厕所乱斗开始。进入厕所的功夫扎实了，乱斗的稳定性才能提高，才能在新赛季上分。一些初斗者过分追求拱门，却忽视了基本的进入厕所技巧。进入厕所是基础，上拱是奇招。进入厕所的方法足够巧妙，才能阻止同学对拱门产生怀疑，从门下窥探。否则，难免落得机房不和，厕所被搜查的结果，就会 mlgb 掉分了。 以上材料对我们颇具启示意义。请结合材料写一篇文章，提现你的感悟和思考。

战神热衷于定义。 对于一个无向正权图 $G$，记 $d(i,j)$ 为在 $G$ 中 $i$ 到 $j$ 的最短路径长度；特别地，若 $i$ 无法到达 $j$，则 $d(i,j)=10^{10^{10}}$。 函数 $f(S,i,j)$ 被定义为 $\sum_{k\in S\backslash \{i\}}[d(i,k)

无

无

#### 样例解释 对于样例第 $1$ 次询问，对于任意一个大小恰为 $1$ 的点集 $S$，$E_H=0$ 时必定合法，因为当 $H$ 边集为空时二分图 $T$ 的边集也必定为空，最大匹配也自然为 $0$，而点集 $S$ 的数目恰为 $n=5$ 个。 #### 数据范围与约定 |测试点编号|$n,m,q$|特殊性质| |:-:|:-:|:-:| |$1\sim 2$|$\le 5$|/| |$3$|$\le 18$|/| |$4$|$\le 500$|/| |$5$|$\le 5000$|/| |$6$|$\le 2\times 10^5$|$\mathbf A$| |$7$|$\le 2\times 10^5$|$\mathbf B$| |$8$|$\le 2\times 10^5$|$\mathbf C$| |$9$|$=2\times 10^5$|$\mathbf D$| |$10$|$\le 3\times 10^5$|/| - 特殊性质 $\mathbf A$：对于所有 $op=1$ 的操作，均有 $k\le 100$。 - 特殊性质 $\mathbf B$：不存在 $op=1$ 的操作。 - 特殊性质 $\mathbf C$：不存在 $op\in\{2,3\}$ 的操作。 - 特殊性质 $\mathbf D$：保证所有数据均在范围内独立均匀随机生成。 对于所有数据，保证 $1\le n,m,q\le 3\times 10^5$，$1\le u_i,v_i\le n$，$1\le w_i\le 10^9$。保证对于所有 $op=1$ 的操作，$1\le k\le n$；对于所有 $op=2$ 的操作，有 $1\le x,y\le n$ 且 $1\le z\le 10^9$；对于所有 $op=3$ 操作，有 $1\le id\le m$ 且 $1\le z\le 10^9$。