noip模拟赛。
因为喝了咖啡没有睡觉。costa的瓶装拿铁真的特别难喝。
T1
图上加边删边，维护连通块大小的积。
一开始以为直接可撤销并查集就可以做。直接去看T2了，看了一会儿回来实现。
想了一下，感觉也许可以直接撤销两个集合的根连接的那条边。
于是写写写。有个函数没递归下去稍微调了一会儿。直接过了前三个大样例。
还好第四个大样例不是很大，直接对着调，发现假掉了。
具体是怎么回事呢：
因为连到上面去所以寄了。
这里我们发现一定要满足原来那个树的结构。
然后觉得非常不可做，于是重新读题。
发现这是个线段树分治板。可以非常容易的转化成在区间内加边的结构。直接维护即可。
我咋又被降智了？
注意到我csp的时候也因为读题浪费了非常多的时间。也许应该加训读题目了。
T4
首先可以把树拍到bfs序上。每层当中又按照 dfs 序排列。
然后可以容易的转化成区间加单点查问题。复杂度 \(O(n \log n * 树高)\)。
上次做过一个转化极其类似的题。好像叫什么常陆茉子。
然后考虑按照x根号分治。
场上确实容易想到根号分治。但是对于\(\sqrt{n} \geq x\)的情况感觉非常难做。
不了了之了。
场后发现确实是根号分治，但是那个部分的做法非常抽象。
尝试询问大手子。终于搞懂了这一块怎么做。
考虑在 dfs 序上做问题。那么就是区间内 \(%x = y\) 的位置 \(+= z\)，将其刻画成 \({x, y}, z\)。
其中 \(x, y < \sqrt{n}\)。
考虑将序列分块，维护 \(f[i][x][y]\) 表示块i内关键字为{x, y}的询问的z之和。
查询时对于单个位置遍历 \(x\)，统计 \(res = \sum f[id][x][dep[i]%x]\) 即可。单次查询复杂度 \(O(\sqrt{n})\)。
直接取块长为 \(\sqrt{n}\) 的话会爆空间。调整一下即可。
有时候这种较为暴力的方法感觉是非常难想的。
思维会被会的套路套牢，暴力思维这块真不太行。/ll