洛谷P4219[BJOI2014]大融合【LCT维护子树】

时空限制 1000ms / 128MB

题目描述

小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻&＃xff0c;一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。

输入格式&＃xff1a;

第一行包含两个整数 N, Q表示星球的数量和操作的数量。星球从 11 开始编号。

接下来的 Q 行&＃xff0c;每行是如下两种格式之一&＃xff1a;

A x y 表示在 x和 y 之间连一条边。保证之前 x 和 y是不联通的。
Q x y表示询问 (x,y) 这条边上的负载。保证 x 和 y 之间有一条边。

输出格式&＃xff1a;

对每个查询操作&＃xff0c;输出被查询的边的负载。

说明

对于所有数据&＃xff0c;1≤N,Q≤1051≤N,Q≤10^51≤N,Q≤105

题目分析

题目中涉及动态加边的操作&＃xff0c;所以马上想到LCT
但是LCT只擅长维护链信息&＃xff0c;而此题要求维护子树&＃xff0c;这就涉及到了LCT一个新的巧妙变化

先做两个定义

• 实儿子&＃xff1a;结点$x$在$splay$中的儿子
• 虚儿子&＃xff1a;与结点$x$在原树中直接相连但在和$x$不在同一个$splay$中

结合LCT的特性我们又知道以下几点

• $x$与它的实儿子在原图中不一定有直接连边
• $splay$维护树链的信息都是维护实儿子的信息
• $x$的实儿子信息包括了实儿子的虚儿子和实儿子的实儿子

那么为了得知$x$原树中子树的信息我们可以

• $access(x)$后返回$x$虚儿子的信息

这是因为$access(x)$后会使$x$没有实儿子

那么为了为了维护虚实儿子的信息&＃xff0c;一些涉及虚实儿子转换的LCT函数就需要修改
以此题中维护子树大小为例&＃xff0c;$Ts[x]$为$x$虚儿子信息&＃xff0c;$size[x]$为原树信息总和

即$Ts[x]$只包含x所有虚儿子(通过轻边指向x)的信息总和
而$size[x]$实际上是$x$在$LCT$中的所有儿子的信息总和(包括辅助树Splay左右儿子的总和以及被轻边所指的虚儿子的总和)

那么要修改的函数应该有三个
首先$access(x)$肯定要改

void access(int x)
{int t&＃61;0;while(x){splay(x);Ts[x]&＃43;&＃61;size[ch[x][1]]-size[t];//加上由实儿子变成虚儿子的size&＃xff0c;减去虚儿子变成实儿子的sizech[x][1]&＃61;t;update(x);t&＃61;x; x&＃61;fa[x];}
}

$link(x,y)$使得$x,y$之间多了一条轻边&＃xff0c;即$x$变成了$y$的虚儿子&＃xff0c;所以$Ts$肯定要改
还有一处不同是$mkrt(y)$&＃xff0c;因为连边后$y$到其$splay$根路径上的结点信息都会改变&＃xff0c;这么做省去更新的麻烦


void match(int x,int y)
{mkrt(x); mkrt(y);fa[x]&＃61;y;Ts[y]&＃43;&＃61;size[x];
}


最后就是更新函数

void update(int x)
{int lc&＃61;ch[x][0],rc&＃61;ch[x][1];size[x]&＃61;size[lc]&＃43;size[rc]&＃43;Ts[x]&＃43;1;//sum[x]&＃61;sum[lc]&＃43;size[rc]&＃43;Tsum[x]&＃43;val[x];//权值总和
}


还有一个$cut(x,y)$似乎也涉及断边&＃xff1f;
事实上$cut(x,y)$断掉的是重边&＃xff0c;也就是实儿子间断开&＃xff0c;并不影响虚儿子信息更新

知道了这么多&＃xff0c;这题其实也就挺裸了
查询也很简单

mkrt(u); access(v); splay(v);
printf("%lld\n",(Ts[u]&＃43;1ll)*(Ts[v]&＃43;1ll));


完整代码

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long lt;int read()
{int f&＃61;1,x&＃61;0;char ss&＃61;getchar();while(ss<&＃39;0&＃39;||ss>&＃39;9&＃39;){if(ss&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ss&＃61;getchar();}while(ss>&＃61;&＃39;0&＃39;&&ss<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;ss-&＃39;0&＃39;;ss&＃61;getchar();}return x*f;
}const int maxn&＃61;500010;
int n,m;
int fa[maxn],ch[maxn][2];
int lzy[maxn],st[maxn],cnt;
lt Ts[maxn],size[maxn];
char ss[5];int isrt(int x)
{return ch[fa[x]][0]!&＃61;x&&ch[fa[x]][1]!&＃61;x;
}void push(int x)
{if(!lzy[x]) return;swap(ch[x][0],ch[x][1]);lzy[ch[x][0]]^&＃61;1; lzy[ch[x][1]]^&＃61;1;lzy[x]&＃61;0;
}void update(int x)
{int lc&＃61;ch[x][0],rc&＃61;ch[x][1];size[x]&＃61;size[lc]&＃43;size[rc]&＃43;Ts[x]&＃43;1;
}void rotate(int x)
{int y&＃61;fa[x],z&＃61;fa[y];int d&＃61;(ch[y][0]&＃61;&＃61;x);if(!isrt(y)){if(ch[z][0]&＃61;&＃61;y) ch[z][0]&＃61;x;else ch[z][1]&＃61;x;}fa[y]&＃61;x; fa[ch[x][d]]&＃61;y; fa[x]&＃61;z;ch[y][d^1]&＃61;ch[x][d]; ch[x][d]&＃61;y;update(y); update(x);
}void splay(int x)
{int top&＃61;0; st[&＃43;&＃43;top]&＃61;x;for(int i&＃61;x;!isrt(i);i&＃61;fa[i])st[&＃43;&＃43;top]&＃61;fa[i];while(top) push(st[top--]);while(!isrt(x)){int y&＃61;fa[x],z&＃61;fa[y];if(!isrt(y)){if((ch[z][0]&＃61;&＃61;y)^(ch[y][0]&＃61;&＃61;x)) rotate(x);else rotate(y);}rotate(x);}
}void access(int x)
{int t&＃61;0;while(x){splay(x);Ts[x]&＃43;&＃61;size[ch[x][1]]-size[t];ch[x][1]&＃61;t;update(x);t&＃61;x; x&＃61;fa[x];}
}void mkrt(int x)
{access(x); splay(x);lzy[x]^&＃61;1;
}void match(int x,int y)
{mkrt(x); mkrt(y);fa[x]&＃61;y;Ts[y]&＃43;&＃61;size[x];
}int main()
{n&＃61;read(); m&＃61;read();for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) size[i]&＃61;1;for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i){scanf("%s",&ss);int u&＃61;read(),v&＃61;read();if(ss[0]&＃61;&＃61;&＃39;A&＃39;) match(u,v);else if(ss[0]&＃61;&＃61;&＃39;Q&＃39;){mkrt(u); access(v); splay(v);printf("%lld\n",(Ts[u]&＃43;1ll)*(Ts[v]&＃43;1ll));}}return 0;
}