当前位置: 代码迷 >> 综合 >> 带权并查集 区间统计
  详细解决方案

带权并查集 区间统计

热度:52   发布时间:2024-01-15 08:16:43.0

带权并查集区间统计

例题:HDU  Zjnu Stadium(模板)

       HDU 3038 How Many Answers Are Wrong

与普通并查集不同是新增加一个属性:

dist[a]:表示a到父亲节点的距离

操作:

在路径压缩时,dis[x]+=dis[t]

在合并时,  dis[r2]=dis[a]+x-dis[b]

发生错误条件:dis[b]-dis[a]!=x

  相关解决方案