[梦回模拟赛]
给一个(n)个点(m)条边的无向图，每次操作给一个点(x)，将(x)和与它相邻的点的点权(+y)，在线询问(x)的点权。
( exttt{subtask 1}) (n,m,q le 3000)
我：噫，这个(mathcal{O}(mq))，水
( exttt{subtask 2}) 菊花图
我：噫，修改中心点就打( exttt{tag})，否则暴力，对于非中心点暴力(mathcal{O}(1))，中心点修改( exttt{tag}mathcal{O}(1)),询问(mathcal{O}(1))，(mathcal{O}(q))。
( exttt{subtask 3}) (forall_{i
ot= 1}space d_i le 10)
我：？
（仔细撕烤）
我：嗷，每次暴力修改次数不超过(10)，是(1)节点就打( exttt{tag})，彳亍！
( exttt{subtask 4}) (n,m,q le 3 imes 10 ^ 5)
我：？
（仔细撕烤）
我：？？？
通过打开题解和询问(color{black}{ exttt{L}}color{red}{ exttt{ightningUZ}})神仙后懂了这玩意叫根号分治。
将度数(le sqrt{m})和(> sqrt{m})的点分开处理。
修改：
- 对于度数(le sqrt{m})的点，暴力修改，最多(sqrt{m})次，(mathcal{O}(sqrt{m}))。
- 对于度数(> sqrt{m})的点，打( exttt{tag})，(mathcal{O}(1))。
询问：
[a_x + sum_{(x,v) in E,d_v > sqrt{m}} exttt{tag}_v
]
处理一下(d_v > sqrt{m})的集合，显然度数超过(sqrt{m})的不超过(frac{m}{sqrt{m}} = sqrt{m})个，(mathcal{O}(sqrt{m}))
时间复杂度(mathcal{O}(qsqrt{m}))
以后会更新亿些题目。