【口胡题解】P7735 NOI2021D1T1 轻重边

· · 个人记录

私 马鹿な子なの 所以想到树剖也想不到染色，只能搞无脑瞎整了。

令每个结点记录一个01值，0代表其与父亲的连边是轻边或没有父亲，1代表该边是重边。

注意操作1的实质：对于某条路径上的所有点，假设这条链是直的（深度严格按DFS序单调），那么就是把所有结点的全部儿子（注意只有儿子）以及链顶结点的01值打成0，之后把链上除了链顶的点的01值打成1。链不是直的情况类似，只不过特殊处理的链顶换成了两端点的LCA。

由于这题是动态的轻重边切换，不难想到LCT，但这货没法很好地维护子树。

直接上AAA Tree。由于原树是静态且无根的，直接随便抓一个根出来之后给每个结点记录父亲是谁。

对于操作1， \text{split（a,b）} ，打一种记录当前结点的特殊标记：

对于实链结点，直接把值搞成1，把标记中的结点改成自己，然后向所有子树（包括实链部分和虚树部分）下传该标记；

对于虚树结点，当且仅当自己的父亲和标记中的结点一致时才接受该标记，将自己的01值打成0，不要修改标记中的结点，之后向所有满足条件的所有子结点下传标记。

之后特殊处理LCA即可。

操作2就是个链求和，太熟悉了，就略去了。

可能需要把树存下来之后DFS一遍才能上AAA Tree。

时间复杂度 O(n \log n) ，但很可能被卡常。

补一种相对正常的写法：

对原树求出重链剖分，之后对每条重链开一颗线段树维护重链上结点的所有轻儿子，之后注意特判即可。时间复杂度 \Theta (n \log n + q \log^2 n) 。