JZOJ6893. 【提高组模拟】小 T 与灵石(stone)题解

这道题需要转化，换根和卡常。
首先将集合中的点拉出来，找它们的直径
不需要什么虚树，随便挑一个集合里的点为根，做一遍dfs，找最远点x（要在集合里），以x为根重复以上操作，找到最远点y，x-y就是题解所谓“集合中点的直径”
然后，$f[i]$值可以转化成i与直径中点距离加上直径长度的一半
问题来了，如果有直径长度单数情况怎么办？
方法1（题解）：发现这时中点在边上，如果中点在x-y边上，考虑新建点z，x，y分别与z连边，长度为1/2，此时z就是中点，为了避免小数，将所有边权*2
方法2（By FK）直径长度/2上取整，此时不必新建点，将x，y看成中点即可
我们在中点处（两个中点则两个中点都要）打上tag标记，代表直径长度/2上取整。
不可能nq复杂度更新f数组，考虑换根。
先从1开始dfs，那么有
$ans[t]=min(min(ans[son]+1),tag[t])$
然后换根，则有
$ans[f[k][1]]=min(ans[f[k][1],ans[t]+1)$
本来需要消除儿子对根的影响，但是min并无所谓，sum就要
其实，理论上呢，这道题应该就结束了。
但是，这道题卡常加上OJ栈空间不够，让它十分恶心！
首先，你会发现自己RE78（如果不WA）
原因：OJ栈空间不够
解决方案：人工栈
然后就是各种各样的TLE
两点间距离可以用ST表预处理，虽然预处理是log的，但查询是O（1）的
此时，如果你还TLE，卡常吧
方法包括但不限于register，inline,if语句改三元运算符等
然后，运气好的话，你就可以AC了
或者依靠OJ的随机摆动，找到快的评测机AC
例如（不是我的）：
正负100ms都是常事，不要惊讶。

本文地址：https://blog.csdn.net/wangyuda123456789/article/details/110174850