首页 > 其他 > 详细

【BZOJ】4530: [Bjoi2014]大融合

时间:2017-10-24 23:41:55      阅读:203      评论:0      收藏:0      [点我收藏+]

【题意】给定n个点的树,从无到有加边,过程中动态询问当前图某条边两端连通点数的乘积,n<=10^5。

【算法】线段树合并+并查集  ||LCT(LCT维护子树信息 LCT维护子树信息(+启发式合并))——嗷嗷待补

【题解】关键在于询问边两端的连通点数。

将原树计算dfs序(强制固定原树形态,方便计算)

设size[x]表示点x所在连通块的大小,那么对于边(u,v),fa[v]=u,有

ans=size[v]*(size[u]-size[v])。

如何实现size的动态计算?

对每个点各自按dfs序维护一棵线段树表示哪些点在此连通块,那么连边就是线段树合并,询问size就是对区间求和。

用并查集维护连通块,连通块中的点指向深度最小的点作为连通块线段树。

 

【BZOJ】4530: [Bjoi2014]大融合

原文:http://www.cnblogs.com/onioncyc/p/7726091.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!