网上找了好几篇题解 , 没几个详细的 , 本蒟蒻太难了 , 最后盯着一个std代码看了好久终于会了.
动态删加边 : lct , 然后需要维护子树中的距离和 , 可反转颜色 .
\(lans\)为子树上黑点到该splay上深度最小的点的距离和 , 由于splay在原树上是一条链 , 所以就是这条实链顶端为根的子树到根的答案 , \(rans\)同理.
\(col\) 存储该点颜色 , 1为黑 , 0为白 .
\(ds\) 为原图这个子树上的黑点数量 , \(ids\) 为x所连接的虚儿子上黑点数量 .
\(val\) 为边权 ( 维护边权=>边变点,维护点权 ) , \(valsum\) 为splay树上的边权和 .
\(ians\) 为虚儿子上黑点到x的距离和 .
代码是正常lct板子 , 但要注意pushup .
如图 , pushup的时候 , \(t[x].lans\)不仅要加上\(t[lc].lans+t[rc].lans+t[x].ians\) , 由于x的右儿子上的点到链顶点还要经过x的左儿子 , x虚子树上的点同理 , 所以要注意pushup的细节 .
上代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 401000
#define ll long long
using namespace std;
int n,m,q;
int cnt;
int sta[maxn],top;
struct lct
{
int fa;
int ch[2];
int rev;
int col;
ll lans,rans; // lans为到splay中深度最小的点的答案,rans同理
ll ds,ids; // 黑点点数, 虚树黑点点数
ll ians; // 虚树到当前点的距离和
ll val; // 边权
ll valsum; // 边权和
}t[maxn];
inline bool notroot(int x) { return t[t[x].fa].ch[0]==x || t[t[x].fa].ch[1]==x; }
inline void reverse(int x) // 由于要维护深度最小的点的答案以及深度最大的点的答案
{ // reverse的时候要先交换,再标记下放
t[x].rev^=1;
swap(t[x].lans , t[x].rans);
swap(t[x].ch[0] , t[x].ch[1]);
}
inline void pushup(int x)
{
t[x].valsum=t[t[x].ch[0]].valsum + t[t[x].ch[1]].valsum + t[x].val;
t[x].ds=t[t[x].ch[0]].ds + t[t[x].ch[1]].ds + t[x].ids + t[x].col;
t[x].lans= t[x].ians + t[t[x].ch[0]].lans + t[t[x].ch[1]].lans
+(t[x].ids + t[t[x].ch[1]].ds + t[x].col) * (t[x].val + t[t[x].ch[0]].valsum);
t[x].rans= t[x].ians + t[t[x].ch[0]].rans + t[t[x].ch[1]].rans
+(t[x].ids + t[t[x].ch[0]].ds + t[x].col) * (t[x].val + t[t[x].ch[1]].valsum);
}
inline void pushdown(int x)
{
if(t[x].rev)
{
reverse(t[x].ch[0]);
reverse(t[x].ch[1]);
t[x].rev=0;
}
}
inline void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=t[y].ch[1]==x;
int w=t[x].ch[k^1];
if(notroot(y)) t[z].ch[t[z].ch[1]==y]=x; t[x].fa=z;
t[w].fa=y; t[y].ch[k]=w;
t[y].fa=x; t[x].ch[k^1]=y;
pushup(y); pushup(x);
}
inline void splay(int x)
{
sta[top=1]=x;
for(register int i=x;notroot(i);i=t[i].fa) sta[++top]=t[i].fa;
while(top) pushdown(sta[top--]); // 手动堆栈
while(notroot(x))
{
int y=t[x].fa;
int z=t[y].fa;
if(notroot(y))
(t[z].ch[0]==y)^(t[y].ch[0]==x) ? rotate(x) : rotate(y);
rotate(x);
}
}
inline void access(int x)
{
for(register int y=0;x;y=x,x=t[x].fa)
{
splay(x);
t[x].ids+=t[t[x].ch[1]].ds-t[y].ds;
t[x].ians+=t[t[x].ch[1]].lans-t[y].lans;
t[x].ch[1]=y;
pushup(x);
}
}
inline void makeroot(int x) { access(x);splay(x);reverse(x); }
inline void split(int x,int y) { makeroot(x);access(y);splay(y); }
inline void link(int x,int y)
{
makeroot(x); makeroot(y); // 记得x和y都要变成根,否则就会因为其父亲没有被更新到而wa
t[x].fa=y;
t[y].ids+=t[x].ds;
t[y].ians+=t[x].lans;
pushup(y);
}
inline void cut(int x,int y) { split(x,y); if(t[y].ch[0]==x) t[x].fa=t[y].ch[0]=0; }
int main()
{
scanf("%d %d %d",&n,&m,&q); cnt=n;
while(m--)
{
int x,y,d; scanf("%d %d %d",&x,&y,&d);
cnt++; t[cnt].val=t[cnt].valsum=d;
link(x,cnt); link(y,cnt);
}
while(q--)
{
char ss[5];int x,y,d;
scanf("%s",ss);
switch(ss[0])
{
case 'L' : scanf("%d %d %d",&x,&y,&d);
cnt++; t[cnt].val=t[cnt].valsum=d;
link(x,cnt); link(y,cnt);
break;
case 'C' : scanf("%d %d",&x,&y);
split(x,y);
d=t[y].ch[0];
cut(x,d); cut(y,d);
break;
case 'F' : scanf("%d",&x);
makeroot(x);
t[x].col^=1;
pushup(x);
break;
case 'Q' : scanf("%d",&x);
makeroot(x);
printf("%lld\n",t[x].lans);
break;
}
}
return 0;
}LOJ #558. 「Antileaf's Round」我们的 CPU 遭到攻击
原文：https://www.cnblogs.com/junble19768/p/12036354.html