link-cut-tree
主要写一写今天写的两个题目总结。
重组病毒，首先看到他的操作相当于，lct换根，lct access。
于是我们观察，这个子树和用lct不好维护呀我去。
所以不要硬想lct了，不然NOI day1t1惨案了！！！！要先想性质！！！
发现这个颜色数，而且这个颜色是一段一段的，所以不难想到可以维护有几次转换颜色。
也就是lct虚边个数。
于此引入lct为时不晚。。
那考虑lct access 复杂度是均摊单次 \(O(\log n)\) 的。所以我们暴力跳实链，更改虚实边，算更改产生的贡献。
发现由于链只有上下两种方向的，所以权值改变的点一定在 dfs 序上的一个区间。。。然后线段树？线段树。。。。。
然后只需要找到这条实链上“下一个”（更浅的点即可），这样splay随便坐一坐即可。
我本来很是疑惑可不可以不用lct，但是发现换根操作真的太麻烦了，所以有换根操作时“适当”考虑lct是可以的。
总结：
lct进行splay操作时一定要pushdown。
实链虚链（除了最后那条）都是直上直下的。（存疑）
最后一点，切记，在树的形态没有发生改变时（除了换根）千万不要随便想lct，现在我看NOI2021 day1t1已经有点想lct了。切记切记。
另外，当跳需要实链而不是access的时候，千万要三思这个是不是lct，复杂度不对！！！。
希望下次碰到NOI day1t1那种题，别被误导，一切题不管多么像，一定先想性质。
当静态树的时候，除了极其特殊情况 重链剖分yyds!
下面这个题就丝毫不会误导人。。。。。。
确实挺有意思的。。。。。
这个题首先看到树的形态这么多变，所以可以放心的lct......
这个题的话，我们考虑我们随意钦定一个环上的点为根，然后维护转移矩阵。
这样尽管我们无法维护时时所有点的值，我们也可以当作每一个点有一个点权，然后每次询问是查询链。。。
接下来考虑如何求解根节点，以及如何维护基环树，（有点繁呀）。
我大概就是照着别人的代码“抄袭”的。
首先基环树就是在钦定的根节点断环成链。然后只需要多维护一个转移到根节点的边即可。
具体解方程我们就查询这条到根节点的边的另一端的点的表达式，然后解方程即可。
换边时候，先切掉一条边，如果基环断裂，那就先加入基环，然后在加入一条边。
不细想会感觉这个很难的样子，实则不然，考虑由于是基环树，如果现在断了基环，那么相当于一棵树被割裂开了。（n个点，n-2条边）
而且是这棵新树的“有向根”没有了父亲，所以把这个新树和原来的根连接即可，原来的根不在是根，而新树的根会获得一条“基环边”。
如果没有段基环，就是把子树独立出去了，这是很simple的情况。
所以这个题还是挺有意思的把。。。。。。。。。。