容易发现新加的边一定是 \(1\) 到某个深度大于 \(i\) 的节点。
考虑每次摧毁深度小于等于 \(i\) 的节点,如果有多个连通块,那么对于 \(b\) 不在的连通块答案是不会变的。
所以如果有两个及以上的连通块中最深的节点是原树上最深的节点,那么答案一定是这个深度。
考虑倒过来从深度大的开始做,对于非目标连通块的答案可以用并查集+可删堆来维护。
对于目标连通块,容易发现答案为当前连通块的直径长度的一半,只要和新加入的节点中最深的节点查询即可。
细节比较少的做法:
维护每个连通块的直径以及最深的节点,然后每次取一个最深节点所在连通块作为 \(b\) 所在的联通块。