洛谷P4172_动态树(Link Cut Tree)

https://www.luogu.com.cn/problem/P4172

一个关键点是把边看成点 ，加一条边u-v，编号为id，则

link(u,id);link(v,id);

每次求出 u 到 v 路径上的最大值，若大于要加的边的边权，则断开路径上的边权最大的边，z再加上要加的边即可。删边操作 与 加边操作 用 LCT 完成。

逆序处理query，将删除操作变成加边操作。

在旋转操作中，只pushup k的父亲p

void rot(int k){

int p=ar[k].fa;

int dir=ar[p].sn[1]==k,id=ar[ar[p].fa].sn[1]==p;

ar[k].fa=ar[p].fa;

if(!isrt(p)) ar[ar[p].fa].sn[id]=k;

ar[ar[k].sn[dir^1]].fa=p,ar[p].sn[dir]=ar[k].sn[dir^1];

ar[p].fa=k,ar[k].sn[dir^1]=p,pushup(p);

}