题意
点修改,链上边权取反;
询问链上边权最大值.
分析
我们把边权存在点上,在建立边与点的对应关系,就可以进行点修改了.
那么我们要修改和查询关于链上的边权又要怎么办呢?
我们注意到如果进行换根操作就不能进行关于链上边权的操作了(这个画画图就能看出来)
所以我们需要一种不用换根的方法.
对于一条链(u,v),首先,Access(v),就会出现下图:
其中v与Root在同一棵辅助树中
再Access(u),直到这种情况:
那么我们的链的边权实际上存在b所在的子树,right(c)所在的子树中.
代码
1 | /****************************************\ |