动态维护树上节点到其他所有点的最长距离
算是 $LCT$ 的模板之一吧
$LCT$ 维护直径，这一题其实可以不用维护直径的，但是我当模板写了
首先我们都知道 $LCT$ 里面的 $splay$ 维护的是一段树链，$splay$ 的子树内的节点恰好为原树上一段连续的链
对每条实链的 $splay$ 维护 $lmx[x],rmx[x],mxs[x],sum[x]$ ，分别表示节点 $x$ 的 splay子树内：
原树上对应的链上深度最浅的节点 $y$ 到原树上该节点(y)子树的最长路径长度 $lmx$
原树上对应的链上深度最深的节点 $y$ 到原树上该节点(y)子树的最长路径长度 $rmx$
原树上该节点 $x$ 子树内的直径 $mxs$
原树上对应的链的节点的权值之和 $sum$
同时我们还要对每个节点维护两个可删堆或者 $multiset$，$H[x],P[x]$ ，分别存该节点虚儿子往下走的最长路径，该节点虚儿子子树内的最长路径
然后我们就可以写出 $splay$ 更新节点的函数：
inline void pushup(int x) { int &lc=c[x][0],&rc=c[x][1]; sum[x]=sum[lc]+sum[rc]+val[x]; ll t=max(0ll,H[x].fir()), L=max(t,rmx[lc])+val[x], R=max(t,lmx[rc])+val[x]; lmx[x]=max(lmx[lc], sum[lc]+R ); rmx[x]=max(rmx[rc], sum[rc]+L ); mxs[x]=max( max( rmx[lc]+R , lmx[rc]+L ) , max(mxs[lc],mxs[rc]) ); mxs[x]=max(mxs[x],P[x].fir()); mxs[x]=max(mxs[x], t+val[x] ); mxs[x]=max(mxs[x], t+H[x].sec()+val[x] ); }
看一眼感觉眼睛花了，不急，慢慢分析
首先 $lc,rc$ 的定义，$sum$ 的维护十分显然
然后定义 $t$ 表示虚儿子贡献的最长路径，注意我们的模板要考虑到节点权值可能为负数的情况，虚儿子可能路径都是负的，所以要和 $0$ 取 $max$
定义 $L$ 表示节点 $x$ 在原树上（包括 $x$）往上不超过实链顶部的原树子树内的最长路径（这里往上包括往 $x$ 的虚儿子）
定义 $R$ 表示节点 $x$ 在原树上（包括 $x$）往下整个原树子树内的最长路径（这里往下也包括往 $x$ 的虚儿子）
那么首先 $lmx[x]$ 可以由 $lc$ 贡献过来，即链不经过 $x$，当然也要考虑经过 $x$，所以还要和 $sum[lc]+R$ 取 $max$
$sum[lc]+R$ 意思就是往上的整条实链和 $x$ 往下最长的链接在一起
同样的，$rmx[x]$ 也是一个道理，可以由 $rc$ 贡献（不经过 $x$） 也可以经过 $x$，经过 $x$ 的最长路程显然 $sum[rc]+L$
然后是恶心的 $mxs$，一大波分类讨论，首先 $mxs$ 也可以由左右儿子更新，然后分别考虑强制经过 $x$ 往上的实链和 $x$ 的往下的实链时的最长路径
再然后就是虚儿子子树了，首先虚儿子子树的路径显然可以由 $P[x]$ 贡献，当然也可以以 $x$ 为起点通向虚儿子的链
最后再考虑一波从 $x$ 的一个虚儿子经过 $x$ 再走向 $x$ 的另一个虚儿子
然后我们就讨论完了
剩下的就是维护 $H$ 和 $P$ 了， $access$ 和 $link$ 的时候注意更新的细节即可
对于 $u$ 的虚儿子 $v$ ，$H[u].push(lmx[v])$ ，即把虚儿子实链上深度最小的节点(就是 $v$ 自己)到整个原树子树的最大路程贡献给 $u$
$P[u].push(mxs[v])$ ，十分显然
其他就是普普通通的 $LCT$，下传翻转标记的时候记得交换 $lmx,rmx$ 即可
手贱写的是可删堆，不开 $O2$ $20$ 到 $30$ 分，开 $O2$ 快 $5$ 倍直接过了是什么操作
自己测用 $set$ 不开 $O2$ ，$50$ 到 $100$ （看常数优化），但是开 $O2$ 却没可删堆开 $O2$ 快是怎么回事？？
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7; const ll INF=1e18; namespace LCT{ int c[N][2],fa[N],sz[N],val[N]; ll sum[N],rmx[N],lmx[N],mxs[N]; bool rev[N]; struct Eraseable_Heap {//可删堆 priority_queue <ll> hp,rub; inline void ins(ll v) { hp.push(v); } inline void del(ll v) { hp.top()==v ? hp.pop() : rub.push(v); } inline ll fir()//求最大值 { while(!hp.empty()&&!rub.empty()&&hp.top()==rub.top()) hp.pop(),rub.pop(); return hp.empty() ? -INF : hp.top();//注意判堆空的情况 } inline ll sec()//求次大值 { ll x=fir(); if(x==-INF) return -INF;//注意判堆空的情况 hp.pop(); ll res=fir(); hp.push(x); return res; } }H[N],P[N]; inline void ins(int u,int v) { H[u].ins(lmx[v]); P[u].ins(mxs[v]); }//节点u加入虚儿子v inline void del(int u,int v) { H[u].del(lmx[v]); P[u].del(mxs[v]); }//节点u删除虚儿子v inline void pushup(int x)//核心的更新函数 { int &lc=c[x][0],&rc=c[x][1]; sum[x]=sum[lc]+sum[rc]+val[x]; ll t=max(0ll,H[x].fir()), L=max(t,rmx[lc])+val[x], R=max(t,lmx[rc])+val[x]; lmx[x]=max(lmx[lc], sum[lc]+R ); rmx[x]=max(rmx[rc], sum[rc]+L ); mxs[x]=max( max( rmx[lc]+R , lmx[rc]+L ) , max(mxs[lc],mxs[rc]) ); mxs[x]=max(mxs[x],P[x].fir()); mxs[x]=max(mxs[x], t+val[x] ); mxs[x]=max(mxs[x], t+H[x].sec()+val[x] ); } inline void pushdown(int x) { if(!x||!rev[x]) return; int &lc=c[x][0],&rc=c[x][1]; rev[x]=0; swap(lc,rc); swap(lmx[x],rmx[x]); if(lc) rev[lc]^=1; if(rc) rev[rc]^=1; } inline void rever(int x) { rev[x]=1; pushdown(x); } inline bool noroot(int x) { return (c[fa[x]][0]==x)|(c[fa[x]][1]==x); } inline void rotate(int x) { int y=fa[x],z=fa[y],d=(c[y][1]==x); if(noroot(y)) c[z][c[z][1]==y]=x; fa[x]=z; fa[y]=x; fa[c[x][d^1]]=y; c[y][d]=c[x][d^1]; c[x][d^1]=y; pushup(y); pushup(x); } void push_rev(int x) { if(noroot(x)) push_rev(fa[x]); else pushdown(x); pushdown(c[x][0]); pushdown(c[x][1]); } inline void splay(int x) { push_rev(x); while(noroot(x)) { int y=fa[x],z=fa[y]; if(noroot(y)) (c[y][0]==x ^ c[z][0]==y) ? rotate(x) : rotate(y); rotate(x); } } inline void access(int x) { for(int y=0;x;y=x,x=fa[x]) { splay(x);/*注意要先splay(x),不然ins(x,y)以后x在splay上的父亲都要更新*/ if(y) del(x,y);//注意特判y是否为0 if(c[x][1]) ins(x,c[x][1]); //注意特判y是否为0 c[x][1]=y,pushup(x); } } inline void makeroot(int x) { access(x); splay(x); rever(x); } inline int findroot(int x) { access(x); splay(x); pushdown(x); while(c[x][0]) pushdown(c[x][0]),x=c[x][0]; splay(x); return x; } inline void split(int x,int y) { makeroot(x); access(y); splay(y); } inline void link(int x,int y)//这里的link有点不一样 { makeroot(x); if(findroot(y)==x) return; makeroot(y); fa[x]=y; ins(y,x); pushup(y);//记得pushup //这里要makeroot(y)不然更新y的时候y在原树往上的整条链的所有实链都要更新 } inline void cut(int x,int y)//cut因为断的是实链所以不要更新H和P { makeroot(x); if(findroot(y)!=x||fa[y]!=x||c[y][0]) return; fa[y]=c[x][1]=0; pushup(x); } } int n,cnt; inline ll query(int x) { LCT::access(x); LCT::splay(x); return LCT::rmx[x]; }//此时x的实链上最深的点就是x int main() { n=read(); char s[7]; int a; for(int i=1;i<=n;i++) { scanf("%s",s); a=read(); if(s[0]=='Q') { printf("%lld ",query(a)-1); continue; } cnt++; LCT::val[cnt]=1; if(a!=-1) LCT::link(a,cnt); } return 0; }