[梦回模拟赛]
给一个\(n\)个点\(m\)条边的无向图，每次操作给一个点\(x\)，将\(x\)和与它相邻的点的点权\(+y\)，在线询问\(x\)的点权。

\(\texttt{subtask 1}\) \(n,m,q \le 3000\)
我：噫，这个\(\mathcal{O}(mq)\)，水

\(\texttt{subtask 2}\) 菊花图
我：噫，修改中心点就打\(\texttt{tag}\)，否则暴力，对于非中心点暴力\(\mathcal{O}(1)\)，中心点修改\(\texttt{tag}\mathcal{O}(1)\),询问\(\mathcal{O}(1)\)，\(\mathcal{O}(q)\)。

\(\texttt{subtask 3}\) \(\forall_{i \not= 1}\space d_i \le 10\)
我：？
（仔细撕烤）
我：嗷，每次暴力修改次数不超过\(10\)，是\(1\)节点就打\(\texttt{tag}\)，彳亍！

\(\texttt{subtask 4}\) \(n,m,q \le 3 \times 10 ^ 5\)
我：？
（仔细撕烤）
我：？？？

通过打开题解和询问\(\color{black}{\texttt{L}}\color{red}{\texttt{ightningUZ}}\)神仙后懂了这玩意叫根号分治。

将度数\(\le \sqrt{m}\)和\(> \sqrt{m}\)的点分开处理。

修改：

• 对于度数\(\le \sqrt{m}\)的点，暴力修改，最多\(\sqrt{m}\)次，\(\mathcal{O}(\sqrt{m})\)。
• 对于度数\(> \sqrt{m}\)的点，打\(\texttt{tag}\)，\(\mathcal{O}(1)\)。

询问：

\[a_x + \sum_{(x,v) \in E,d_v > \sqrt{m}} \texttt{tag}_v \]

处理一下\(d_v > \sqrt{m}\)的集合，显然度数超过\(\sqrt{m}\)的不超过\(\frac{m}{\sqrt{m}} = \sqrt{m}\)个，\(\mathcal{O}(\sqrt{m})\)

时间复杂度\(\mathcal{O}(q\sqrt{m})\)

以后会更新亿些题目。