前言&&思想
一些给定树上一些点集，要处理和该点集有关的询问（例如和点集关系，点集选择限制）的题目，
很多子树没有变化，暴力没有意义。
提取出有关的点和路径，构成虚树
虚树上DP等等，难点往往在于找到非虚树部分的答案。
建立
1.暴力sort再sort
LCA一般都要用，所有点按照dfn序sort，相邻两点的LCA就是所有涉及到的LCA
注意，LCA可能算重！
然后所有的点（包括LCA）再按照dfn sort
利用括号序，用栈模拟，如果新来的点不在栈顶的子树范围内[dfn,dfn2]就弹出栈顶
2.LCT，还支持换根
换根LCA：以r为根，a，b的lca为lca(a,b)⊕lca(a,r)⊕lca(b,r)（伪LCA会被计算两次就消了）
换根dfn序：可以分类讨论子树范围，但是，虚树要sort，你怎么重载小于号？必须有dfn序，，但是不能立刻求出来。
所以，换根大师LCT闪亮登场！
设当前根是rt
access每个点
恰好连到和rt在一条链上就停止，在这个点上打标记
最后找每个点到根路径上第一个有标记的点，就是这个点的父亲。
复杂度还是logn，常数大
例题
保卫王国加强版
对n个点进行限制
把转移变成矩阵
然后倍增维护
和动态DP有相似之处
消耗战
世界树
WC2018 通道
学了边分治再写
Codechef Sad Pairs加强版
• 给出一张图，每个点都有颜色
• 对每个点求出
• 如果把这个点从图中删去
• 那么会有多少对不连通的同色点对
•