首页 > 代码库 > [Bjoi2014]大融合
[Bjoi2014]大融合
[Bjoi2014]大融合
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 394 Solved: 244
[Submit][Status][Discuss]
Description
小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。
这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够
联通的树上路过它的简单路径的数量。
例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因
为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。
现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的
询问。
Input
第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。
接下来的Q行，每行是如下两种格式之一：
A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。
Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。
1≤N,Q≤100000
Output
对每个查询操作，输出被查询的边的负载。
Sample Input
8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8
Sample Output
6
LCT维护子树信息
维护两个和，sum：总的和（虚边+实边），cnt：虚边和
需要修改的操作：
access：cnt+=sum[ch[x][1]]-sum[t] x原来的实边变为虚边，加上他，t由虚边变为实边，减去他
link：x练到y上，x的子树全部成为y的虚子树，所以cnt[y]+=sum[x]
#include<cstdio>#include<algorithm>#include<iostream>using namespace std;#define N 1000001int ch[N][2],fa[N],sum[N],st[N],top,cnt[N];bool tag[N];struct LCT{ bool isroot(int x) { return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;} void update(int x) { sum[x]=1+cnt[x]+sum[ch[x][0]]+sum[ch[x][1]]; } int getson(int x) { return ch[fa[x]][1]==x; } void down(int x) { if(tag[x]) { tag[x]^=1; tag[ch[x][0]]^=1; tag[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]); } } void rotate(int x) { int y=fa[x],z=fa[y],l=getson(x),r=l^1; if(!isroot(y)) ch[z][ch[z][1]==y]=x; ch[y][l]=ch[x][r]; ch[x][r]=y; fa[x]=z; fa[y]=x; fa[ch[y][l]]=y; update(y); } void splay(int x) { st[top=1]=x; for(int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i]; for(int i=top;i;i--) down(st[i]); while(!isroot(x)) { int y=fa[x]; if(!isroot(y)) rotate(getson(x)==getson(y) ? y : x); rotate(x); } update(x); } void access(int x) { int t=0; while(x) { splay(x); cnt[x]+=sum[ch[x][1]]-sum[t]; ch[x][1]=t; update(x); t=x; x=fa[x]; } } void make_root(int x) { access(x); splay(x); tag[x]^=1; } void split(int x,int y) { make_root(x); access(y); splay(y); } void link(int x,int y) { split(x,y); cnt[y]+=sum[x]; fa[x]=y; update(y);}};LCT lct;int main(){ int n,m; scanf("%d%d",&n,&m); fill(sum+1,sum+n+1,1); char s[2]; int x,y; while(m--) { scanf("%s%d%d",s,&x,&y); if(s[0]==‘A‘) lct.link(x,y); else lct.split(x,y),printf("%lld\n",1ll*sum[x]*(sum[y]-sum[x])); }}
[Bjoi2014]大融合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。