2.29闲话 & solution 『任无数/花开花落之后/你仍君临芸芸众生』

明天就省选了，我咋啥也不会

最破防的一集

一道LCT调了一下午没调出来

最后发现是 min 和 max 取反了

改完之后发现自己的访问有问题，如果有 0 边权我就会直接返回LLONG_MAX

啊哈哈，我调了一下午，发了7个帖子

然后校内OJ过了，POJ因为只有C++98所以 CE 了

写个简要题解吧

• [POJ3237] 树的维护

  这道题与一般的 LCT 似乎有一点不同

  给的不是点权，那怎么办呢

  错误思考示范

  诶树剖的时候好像也有这个问题，是不是可以参考树剖

  用儿子节点记录其到其父亲的边权，然后云云

  但是这样有个问题，就是说 LCT 使用 splay 维护的，splay 是会破坏原本的父子关系的

  那么这个做法宣告破产了wwwww

  根据 FalshHu 的讲解，我们可以得知有两种解法

  1. 把边置于 LCT 外，然后在 LCT 节点中维护父边和重子边的编号，需要更新信息时从外部获取

     但是这种方法有一个问题：需要在access操作，Link操作，Cut操作都进行修改，很麻烦

  2. 建立额外的节点

     我们可以建立额外的表示边的节点，然后把表示点的节点的权值都设为\(0\)

     这样我们就可以把原本的边权转化为点权来让 LCT 去维护

     此时普通的 Link 和 Cut 都存在一些问题

     Link 和 Cut 操作只能添加/删除一条边，而不能删除代表边权的边

     解决方法也很简单，直接 Link/Cut 两次即可

     • 核心代码

       link(a[i].x,a[i].id);
       link(a[i].id,a[i].y);
       

  我们通常选择建立代表边的节点，也就是第二种方法

  在本题中建立边的方式如下

  for(int i=1;i<n;++i){
      FastI>>x>>y>>val[i+n];
      link(x,i+n);
      link(y,i+n);
  }
  

  这里的求 max 后取反如何维护呢？我们发现只要取 min 即可，这样取相反数后的结果就是 max

  那么这道题就非常容易的做出来了