首页 > 代码库 > BJOI2014 大融合
BJOI2014 大融合
3766. 【BJOI2014】大融合 (Standard IO)
Time Limits: 1000 ms Memory Limits: 262144 KB
先把所有边连起来，然后排dfs序来判断每次连的点中哪个作为父亲，哪个作为儿子。然后进行操作，用并查集来维护各个连通块，用链剖维护size，每个更新这个连通块内所有父亲的值，用倍增找这个连通块内离它最远的父亲。
#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;struct tree{ int x,z,q,bz;}tr[500011];bool vis[100011];int top[100011],son[100011],dfn[100011],num[100011],size[100011];int g[100011],y[200022],next[200022],f[100011],fa[100011],kind[100011],nn[100011];int edge[100011][3],fat[100011][18];char s[11];ll ap,ple,xzq;int i,j,n,q,x,z,t,tt,tot,e;void swap(int &a,int &b){ int t; t=a; a=b; b=t;}int find(int r){ if(f[r]==r)return r; else f[r]=find(f[r]); return f[r];}void star(int i,int j){ tt++; next[tt]=g[i]; g[i]=tt; y[tt]=j; tt++; next[tt]=g[j]; g[j]=tt; y[tt]=i;}void build_chain(int root){ int x; x=root; while(x!=0){ num[x]=++tot; top[x]=root; x=son[x]; }}void Dfs(int x,int faf){ int j,k; size[x]=1; fa[x]=faf; fat[x][0]=faf; vis[x]=true; dfn[x]=++t; j=g[x]; while(j!=0){ k=y[j]; if(!vis[k]){ Dfs(k,x); size[x]+=size[k]; if(size[k]>size[son[x]]){ if(son[x])build_chain(son[x]); son[x]=k; } else build_chain(k); } j=next[j]; }}void down(int t){ if(tr[t].x==tr[t].z)return; if(tr[t].bz){ tr[t+t].bz+=tr[t].bz; tr[t+t].q+=tr[t].bz; tr[t+t+1].bz+=tr[t].bz; tr[t+t+1].q+=tr[t].bz; tr[t].bz=0; }}void build(int l,int r,int t){ int mid; if(l==r){ tr[t].x=l; tr[t].z=r; tr[t].q=1; tr[t].bz=0; nn[l]=t; return; } mid=(l+r)/2; tr[t].x=l; tr[t].z=r; build(l,mid,t+t); build(mid+1,r,t+t+1);}void insert(int t,int l,int r,int x){ int mid; down(t); if(tr[t].x==l&&tr[t].z==r){ tr[t].q+=x; tr[t].bz+=x; return; } mid=(tr[t].x+tr[t].z)/2; if(r<=mid)insert(t+t,l,r,x); if(l>mid)insert(t+t+1,l,r,x); if(l<=mid&&r>mid){ insert(t+t,l,mid,x); insert(t+t+1,mid+1,r,x); }}int ask(int t,int x){ int mid; down(t); if(tr[t].x==tr[t].z)return tr[t].q; mid=(tr[t].x+tr[t].z)/2; if(x<=mid)return ask(t+t,x); else return ask(t+t+1,x);}int Finn(int x,int z){ int i,q; q=z; for(i=17;i>=0;i--){ f[fat[q][i]]=find(f[fat[q][i]]); if(f[fat[q][i]]==x)q=fat[q][i]; } return q;}void change(int x,int z,int q){ int t; while(x!=0){ if(top[q]==top[x]){ insert(1,num[q],num[x],z); return; } else{ insert(1,num[top[x]],num[x],z); x=fa[top[x]]; } }}int main(){ scanf("%d%d",&n,&q); for(i=1;i<=q;i++){ scanf("%s",&s); scanf("%d%d",&x,&z); edge[i][1]=x; edge[i][2]=z; if(s[0]==‘A‘)star(x,z); if(s[0]==‘A‘)kind[i]=1; else kind[i]=2; } memset(vis,false,sizeof(vis)); for(i=1;i<=n;i++){ if(!vis[i]){ Dfs(i,0); build_chain(i); } } for(i=1;i<=17;i++){ for(j=1;j<=n;j++){ fat[j][i]=fat[fat[j][i-1]][i-1]; } } build(1,n,1); for(i=1;i<=n;i++)f[i]=i; for(i=1;i<=q;i++){ if(kind[i]==1){ if(dfn[edge[i][1]]>dfn[edge[i][2]])swap(edge[i][1],edge[i][2]); x=find(f[edge[i][1]]); z=find(f[edge[i][2]]); if(x!=z)f[z]=x; e=Finn(x,edge[i][2]); ple=ask(1,num[edge[i][2]]); change(edge[i][1],ple,e); } else{ if(dfn[edge[i][1]]>dfn[edge[i][2]])swap(edge[i][1],edge[i][2]); f[edge[i][1]]=find(f[edge[i][1]]); ap=ask(1,num[f[edge[i][1]]]); ple=ask(1,num[edge[i][2]]); xzq=(ap-ple)*ple; printf("%lld\n",xzq); } }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。