FJ2016集训 day5

2016年7月7日1,4984

打了个酱油,身败名裂0。0

1 冷战

1.1 题目大意

给定一副 N 个点的图。动态的往图中加边,并且询问某两个点最早什么时候联通。

1.2 题解

考虑并查集。并查集实际上维护了一棵树。那么假如我们按秩合并,这棵树的深度是 O(log n) 的。我们将一个点连向其父亲的边权设为这条边加入的时间,那么每次询问时,暴力查询树上从 uv 所经过边权的最大值即可。时间复杂度为 O(n log n),常数较小。假如写了常数较大的可以得到 80 分。

  • ct2016年7月7日 下午10:29 回复

    orz hzwer,今天终于看到您了。后两题没看见多组数据成功爆成100的傻逼路过。

    #1  
  • 黄学长是要成为海贼王的男人!2016年7月8日 上午10:13 回复

    强制在线啊QwQ 那我只会LCT QwQ

    #2  
    • hzwer2016年7月8日 上午11:44 回复
      admin

      会被卡2333

      #21
      • 黄学长是要成为海贼王的男人!2016年7月8日 下午12:09 回复

        明明 明明复杂度都是一样的!

        #22