前言

其实很久以前就学过了，做完两个题后巨大的码量让juruo滚回去复习\(NOIP\)知识点

再过三个月就要省选了，来复习一下

作用

说到底，虚树就是单独拉出来几个点建个树优化树形动规

理解

我们按dfs序排序，这里就为了简化操作

建树时堆到栈里建，由于dfs序排列，\(a_i\)与栈顶的\(lca\)不可能是\(a_i\)

所有有两种情况：

1.\(lca\)为栈顶，直接忽略

2.栈顶与\(a_i\)分别位于\(lca\)的两棵子树，此时我们应该结束栈顶的子树遍历了

\(~~~\)因为\(a_i\)>栈顶，栈顶这棵子树的结点再也不会来了，所以我们考虑把这个结点弹出来

\(~~~\)但是我们把栈顶弹出前，总得把它跟父节点连起来吧，它的父节点除能是\(lca\)外，还能是栈顶下面这个节点

\(~~~\)如下图，两种情况

\(~~~~~~1.lca\)为栈顶的父节点时，如\(lca1\)

\(~~~~~~2.tp-1\)为栈顶的父节点时，如\(lca2\)

sort(a+1,a+1+k,cmp);sta[tp]=1;for(int i=1;i<=k;++i){    int lca=LCA(a[i],sta[tp]);    while(dep[sta[tp]]>dep[lca]){        if(dep[sta[tp-1]]
    
     1){    add(sta[tp-1],sta[tp]);    tp--;}