本文采用 BY-NC-SA 协议发布。
要求：给你一棵树，边带权，每次断边连边（保证合法且仍是树），在线求每次修改后的直径。
LCT
（咕）
Top Tree
拆边，然后用 negiizhao 论文里的方法维护。
实现时注意，翻转标记会影响合并的信息，要 swap 一下。
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <cassert>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
using std::cin; using std::cout;
using ll = long long;
struct Info{
ll ml, mr, mm, lr;
// m: inside cluster
// l: min dep
// r: max dep
Info(){}
Info(int a, int b, int c, int d):ml(a), mr(b), mm(c), lr(d){}
Info operator>>(Info b){ // COMPRESS
Info ans;
ans.mm = std::max({mm, b.mm, mr + b.ml});
ans.ml = std::max(ml, lr + b.ml);
ans.mr = std::max(b.mr, b.lr + mr);
ans.lr = lr + b.lr;
return ans;
}
Info operator<<(Info b){ // RAKE
Info ans;
ans.mm = std::max({mm, b.mm, ml + b.ml});
ans.ml = std::max(ml, b.ml);
return ans;
}
};
constexpr int N = 2e5;
namespace TopTree{ // }{{{
enum NT{ COMPRESS, RAKE };
struct Node{
Node *fa, *ls, *ms, *rs;
Info sum; // heavy_info, light_info
int len; // to fa
NT typ;
bool rev;
} nil_, *nil = &nil_, nds[N*2];
std::vector<int> rubbish;
Node *nnod(){
static int cnt = 0;
if(rubbish.empty()) return nds + cnt++;
Node *p = nds + rubbish.back();
rubbish.pop_back();
return p;
}
void erase(Node *x){ rubbish.push_back(x - nds); }
void flip(Node *x){ x->rev ^= 1; std::swap(x->sum.ml, x->sum.mr); }
bool nroot(Node *x){ return x->fa->ls == x || x->fa->rs == x; }
bool isrs(Node *x){ return x == x->fa->rs; }
void pushup(Node *x){
if(x->typ == COMPRESS){
Info my = Info(x->ms->sum.ml + x->len, x->ms->sum.ml + x->len,
std::max({x->ms->sum.mm, x->ms->sum.ml + x->len}), x->len);
x->sum = x->ls->sum >> my >> x->rs->sum;
if(x->rev) std::swap(x->sum.ml, x->sum.mr);
} else {
x->sum = x->ls->sum << x->ms->sum << x->rs->sum;
}
}
void pushdown(Node *x){
if(x->rev == false || x == nil) return;
x->rev = false;
flip(x->ls);
flip(x->rs);
std::swap(x->ls, x->rs);
pushup(x);
}
void pushdddd(Node *x){
if(nroot(x)) pushdddd(x->fa);
pushdown(x);
}
void setfa(Node *x, Node *f, int pos){
if(x != nil) x->fa = f;
if(pos == 0) f->ls = x;
else if(pos == 1) f->rs = x;
else f->ms = x;
}
void rotate(Node *x){
if(x == nil || !nroot(x)) return;
Node *y = x->fa, *z = y->fa;
if(z != nil){
if(z->ls == y) z->ls = x;
if(z->ms == y) z->ms = x;
if(z->rs == y) z->rs = x;
}
if(isrs(x)){
setfa(x->ls, y, 1);
setfa(y, x, 0);
} else {
setfa(x->rs, y, 0);
setfa(y, x, 1);
}
x->fa = z;
pushup(y);
pushup(x);
}
void splay(Node *x, Node *to = nil){
pushdddd(x);
for(Node *y; y = x->fa, nroot(x) && y != to; rotate(x)){
if(y->fa != to && nroot(y)){
rotate(isrs(y) ^ isrs(x) ? x : y);
}
}
}
void unuse(Node *x){
assert(x->typ == RAKE);
if(x->ls == nil){
setfa(x->rs, x->fa, 2);
} else {
Node *p = x->ls;
pushdown(p);
while(p->rs != nil) p = p->rs, pushdown(p);
splay(p, x);
setfa(x->rs, p, 1);
setfa(p, x->fa, 2);
pushup(p);
pushup(x->fa);
}
erase(x);
}
void splice(Node *x){
splay(x);
Node *y = x->fa;
splay(y);
pushdown(x);
if(y->rs != nil){
std::swap(x->ms->fa, y->rs->fa);
std::swap(x->ms, y->rs);
pushup(x);
} else {
setfa(x->ms, x->fa, 1);
unuse(x);
}
pushup(y);
}
void access(Node *x){
splay(x);
if(x->rs != nil){
Node *y = nnod();
y->len = y->rev = 0;
y->typ = RAKE;
setfa(x->ms, y, 0);
setfa(x->rs, y, 2);
x->rs = y->rs = nil;
setfa(y, x, 2);
pushup(y);
pushup(x);
}
Node *p = x;
while(p->fa != nil){
splice(p->fa);
p = p->fa;
pushup(p);
}
splay(x);
}
void mkroot(Node *x){ access(x); flip(x); }
void expose(Node *x, Node *y){ mkroot(x); access(y); }
Node *findrt(Node *x){
access(x);
pushdown(x);
while(x->ls != nil) x = x->ls, pushdown(x);
splay(x);
return x;
}
void link(Node *x, Node *y){
//if(findrt(x) == findrt(y)) return;
access(x);
mkroot(y);
setfa(y, x, 1);
pushup(x);
}
void cut(Node *x, Node *y){
expose(x, y);
if(y->ls != x || x->rs != nil) return;
x->fa = y->ls = nil;
pushup(y);
}
} // {}}}
namespace m{ // }{{{
int in, iq;
using TopTree::Node;
using TopTree::nds;
using TopTree::nil;
std::unordered_map<ll, Node*> lnk;
ll geted(int x, int y){
if(x > y) std::swap(x, y);
ll ed = ll(x) << 32 | y;
return ed;
}
ll sum_edge;
void iN(){
cin.tie(0)->sync_with_stdio(0);
cin >> in >> iq;
UP(i, 0, in){
Node *p = TopTree::nnod();
p->fa = p->ls = p->ms = p->rs = nil;
p->typ = TopTree::COMPRESS;
}
UP(i, in, in+in-1){
int ix, iy, iw; cin >> ix >> iy >> iw;
ix--, iy--;
sum_edge += iw;
ll ed = geted(ix, iy);
Node *p = TopTree::nnod();
p->fa = p->ls = p->ms = p->rs = nil;
p->typ = TopTree::COMPRESS;
p->len = iw;
p->sum = {iw, iw, iw, iw};
TopTree::link(nds+ix, p);
TopTree::link(nds+iy, p);
lnk[ed] = p;
}
TopTree::access(nds);
cout << nds->sum.mm << '\n';
}
void work(){
while(iq--){
int ix, iy, ip, q, iw;
cin >> ix >> iy >> ip >> q >> iw;
ix--, iy--, ip--, q--;
ll olded = geted(ix, iy);
ll newed = geted(ip, q);
Node *p = lnk[olded];
lnk.erase(olded);
sum_edge -= p->len;
TopTree::cut(nds+ix, p);
TopTree::cut(nds+iy, p);
p->len = iw;
sum_edge += iw;
TopTree::link(nds+ip, p);
TopTree::link(p, nds+q);
lnk[newed] = p;
cout << p->sum.mm << '\n';
}
}
} // {}}}
int main(){m::iN(); m::work(); }