LCT

今天有点人品，T1的50pts暴力怒压正解。。这数据。。不言而喻 $\text{score: 100 + 0 + 0 = 100 rk: 7/36}$ Problem A：时间管理带师题目描述众所周知，罗老师是时间管理带师 因为罗老师是时间管理带师，所以他的时间是以东为单位的 具体来讲，罗老师一天有nn东的时间 现在有很多妹子想跟罗老师约会 奇特的，她们每天总会提出两段约会时间（可能相同，代表一种），并且每天提出的总是一样的。 她们提出的约会时间形式形如i,j,代表希望在[i东,(i+1)东)[i东,(i+1)东)或[j东,(j+1)东)[j东,(j+1)东)与罗老师进行约会。 当然，罗老师可以这两段时间都与这个妹子约会,只选择一段，或者伤心地抛弃。 那么，作为时间管理带师的罗老师，每天会选择尽可能多的妹子进行约会 但你一定要注意,罗老师最近并不打算进行多人运动，所以他不会在1东的时间同时与两个或多个妹子约会 罗老师并不脸盲，与一个妹子约会2次并不能算成”2”次的贡献，只能是”1” 罗老师是时间管理带师，只要满足以上条件，他就可以安排好他的时间，不用担心别的 而且,每天可能会有新的 ...

（貌似整个代码不能用 $makeroot$ ？是因为是有根树？） 因为是区间操作，所以可以考虑在区间内与区间外的差异 对于操作 $1$ ，可以看作一个生成节点包含了到下一个 $1$ 操作之间长出的节点，那么对于一个操作 $l, r$ ，相当于是在 $l$ 处将当前生成节点及其包含的节点整个移植到它更改后的位置，到 $r + 1$ 时再移植回去，所以可以考虑将一个 $1$ 操作分解为两个操作（一个移植，一个移植回去），故可以将所有操作按端点、时间排序（以及同位置修改操作必定在查询操作前，因为可以先把树建完再查询对结果没有影响），扫描一遍即可 同时，为了方便移植，将每个生成节点看作新建的一个虚点 对于操作 $0$ ，直接在虚点下 $link$ 即可，因为就算已经建了一些对于当前操作不存在的虚点，也不会对答案造成影响 对于操作 $2$ ，无法正面在 $LCT$ 上算出两点的距离，故可考虑差分，得到 $Ans = Sum_x + Sum_y - 2 * Sum_{lca}$ ，其中实点贡献为 $1$ ，虚点贡献为 $0$ 对于求 $LCA$ ，先 $access (y)$ ，再在 $acces ...

题意每个点有各自的权值，要求维护操作：动态加边、动态修改权值、询问在每个点只能经过一次的情况下两点间路程中的最大权值和 题解首先对于一个静态的图，将其缩点，可以得到一棵树，那么两点间询问的答案即为它们之间经过的 $BCC$ 的权值和 支持动态加边，就需要用到 $LCT$ 去维护 $BCC$ 如果两个点所在 $BCC$ 在不同树上，那么直接连边即可；反之，则说明形成了环，就暴力将这条链拖出来，用选定一个标准节点，用并查集将链上其它节点连到标准节点上，容易证明，这样的复杂度是均摊 $O (\log n)$ 的 查询即修改容易实现，不加赘述 注意，此题没有删边，所以 $findroot$ 可用另一个并查集代替，不然会 $T$ 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969 ...