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

一個關(guān)鍵點是把邊看成點?，加一條邊u-v，編號為id，則

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

每次求出 u 到 v 路徑上的最大值，若大于要加的邊的邊權(quán)，則斷開路徑上的邊權(quán)最大的邊，z再加上要加的邊即可。刪邊操作 與 加邊操作 用 LCT 完成。

逆序處理query，將刪除操作變成加邊操作。

在旋轉(zhuǎn)操作中，只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);

}