9.11集训

第一个 软件安装 是一个树形dp加tarjan缩点

注意缩点完成之后建立新图的时候，要与跟连边

第二个 股票交易

如果不优化的话，上来一大堆讨论

其中发现有两种情况可以用单调队列来优化

第三个 消耗战

是一个虚树+树形dp

这个树形dp很好写，但是虚树不好搞

大致思想：每次询问，我们如果对原树进行遍历的话，复杂度过高，无法接受

考虑将其中有用的点搞出来，我们遍历的时候，对这些点遍历即可，可大大缩减时间复杂度

考虑如何构建虚数：

构建一个栈，在不断弹栈的过程就是建立虚树的过程（先按照dfn序排序，防止反复跳

当前：sta[1] = root, sta[top]

新加进来一个x，考虑x与原来sta[top]的影响，对他俩求一个lca，如果lca为sta[top]，直接加进来就可以了

如果不是的话，大力讨论