对 dfn 序开数据结构（如线段树），每个结点 \(p\) 维护对应 dfn 序区间内所有存在的点所构成的虚树大小 \(sz_p\)，需要维护区间内所有存在的点中 dfn 序最大点 \(rv_p\) 和最小点 \(lv_p\)、区间内所有存在点的 LCA \(lca_p\).
考虑合并左右儿子 \(ls, rs\)，按两棵虚树是否相交分讨，先考虑相交的情况，容易证明两棵虚树的交一定形如一条链注，进一步的，即为 \(rv_{ls}\) 到 \(lca_{ls}\) 的链 与 \(lv_{rs}\) 到 \(lca_{rs}\) 的链的交，而链交是好求的，于是合并后的虚树大小即为 \(sz_{ls}+sz_{rs} + dep_{lca_{ls}} + dep_{lca_{rs}} - dep_{\operatorname{LCA}(rv_{ls}, lv_{rs})} - dep_{\operatorname{LCA}(lca_{ls}, lca_{rs})} - 1\).
发现不交的情况下式子是一样的，其实可以考虑在左右儿子的虚树中都加入从 \(lca\) 到根的链，这样就只有相交的情况了，且交是一条一端为根的链，求出虚树并后减去新的 \(lca\) 到根的链长即可.
可以使用 dfs 序 + st 求 LCA.
注：如果不为一条链，即交有两个叶子，这意味着被合并的两个点集都分别在这两个叶子对应的子树内有点，两个叶子对应子树的 dfn 区间不交，于是被合并的两个点集的 dfn 区间出现相交，即导出矛盾.
标签：rs,dep,trick,dfn,ls,lca,动态,虚树 From： https://www.cnblogs.com/0922-Blog/p/18180786/trick-to-maintain-the-size-of-virtual-tree