SD2022 第二轮省队集训

day 1

T1
https://www.luogu.com.cn/problem/P7163

/(f(u,0/1,0/1/2)/) 表示走完 /(u/) 的子树，/(u/) 的子树全都开启，/(u/) 是关闭/开启，/(u/) 内部有 /(0/1/2/) 个路径端点，的最小路径长度
然后转移的时候要加入 /(u/) 的一个儿子 /(v/)
端点的个数就是背包，然后考虑一下哪些点被多走了，考虑完如果 /(v/) 被关闭了，那么再走一个 /(u-v/) 补一下

T2
https://www.luogu.com.cn/problem/P7164

T3
https://www.luogu.com.cn/problem/P7172

如果两个点不呈祖先关系，那么他们的 /(/operatorname{lca}/) 一定在那 /(n/) 个关键点中
所以只要找出每个给出的点往上的第一个关键点，然后拿着这两个关键点在关键点的虚树上跑 /(/operatorname{lca}/) 即可
找关键点的话，从上往下维护关键点是需要插入点，然后每个版本只有 /(O(1)/) 个位置发生变化，就是可持久化平衡树
但是可以从下往上变成删点，就能用可持久化线段树了