Top Tree 解决动态直径问题
EnofTaiPeople
·
·
题解
如果你还不会 $\text{Top-Tree}$，可以到[这里](/blog/502410/sone1-imaglct-satt-develop-p5649)学习。
对于 $\text{Compress-Tree}$，我们维护，簇中直径、簇中到左右端点的最远距离，即可做到轻松合并，注意要记录簇链长度。
对于 $\text{Rake-Tree}$ 也很好维护，直接考虑将两棵子树最深点（相当于到左端点最远距离）组成的直径，十分方便。
合并部分代码：
```cpp
struct dat{
ll l,m,r,ln;//左端点距离，直径长度，右端点距离，簇链长度
dat operator+(dat z){
return {max(l,ln+z.l),max({m,z.m,r+z.l}),max(r+z.ln,z.r),ln+z.ln};
}
}sm[N];
dat datad(dat x,dat y){
return {max(x.l,y.l),max({x.m,y.m,x.l+y.l})};
//rake-tree 的合并
}
dat gdat(int x){
if(ms)return{sm[ms].l+w[x],max(sm[ms].m,sm[ms].l+w[x]),sm[ms].l,w[x]};
else return{w[x],w[x],0,w[x]};
//将 rake-data 转换成 compress-data
}
void pp(int x){
if(x>n){//rake-pushup
if(ls&&rs)sm[x]=datad(sm[ls],sm[rs]);
else sm[x]=sm[ls|rs];
}else{//compress-pushup
sm[x]=sm[ls]+gdat(x)+sm[rs];
}
}
```
发现这就是普通的 $\text{Self-adjusting-Top-Tree}$ 操作，于是时间复杂度为 $O(q\log_2n+n)$，空间复杂度为 $O(n)$，支持在线。
劣势：常数较大，需要 $333ms$，而最优解只要 $237ms$，可能对于少数人来说并不好写，也不好调试，即使我只要一小时写，半小时调。
优势：扩展性强，欧拉序做法似乎不能支持负边权，而这个做法不仅可以支持负权，还能换父亲（暂时不知道怎么换根）。
常数大是 $\text{SATT}$ 最大的缺陷，但是这题并不需要更改树的形态，所以可以采用全局平衡二叉树，这样让常数变得优秀，只需要 $213ms$，是目前的最优解（$\text{test on 2022-11-07}$，超过了所有线段树做法）。
其实 $\text{SATT}$ 更好写！不到 $3.0K$！全局平衡二叉树由于需要预处理建树，所以时间复杂度为 $O((n+q)\log_2n)$，每次修改只要不停地跳父亲 `pushup`，常数很小。