虚树
2018第一篇博客啦啦啦！！！
虚树可以处理一些树上的问题中有一些关键点，并且所有询问的点数之和不是很大的问题。
设
对于每一个询问，将询问点按照dfs序排序，那么所有相邻两个点的LCA的集合便是两两点对的LCA的集合。因为LCA(x,z)一定是LCA(x,y)或LCA(y,z)。
把询问点以及所有的LCA叫作关键点。
然后有些与计数等等有关的题可能还要加上根节点，方便起见，就每次都加入根节点。
那么所有关键点的个数总和是
的。
点全都处理好了，接下来就是建边了。
将关键点以及LCA一起按照dfs序排序。
用一个栈维护根节点到当前关键点的一条链。
维护就是若栈顶不是当前点的祖先就出栈，直到栈顶是当前点的祖先。
怎么判断是不是当前点的祖先呢，可以用dfs序中的入栈以及出栈时间戳，但我直接用LCA，因为前面处理关键点就已经
了，渐进复杂度没区别的。（好吧是我懒，懒得写出栈时间戳，虽然就两句话）
然后栈顶元素向当前点连一条边，边权……不同的题都不同的，所以就要发挥你的聪明才智了。
还有一点就是边表要重复使用，不能每次全清空。
模板（每次询问）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
int cnt; scanf("%d", &cnt); for (int i = 1; i <= cnt; i++) { scanf("%d", &x[i]); cc[i] = x[i]; flag[cc[i]] = 1; } cnt++; x[cnt] = 1; cc[cnt] = 1; int tmp = cnt; std::sort(x + 1, x + cnt + 1, comp); cnt = std::unique(x + 1, x + cnt + 1) - x - 1; for (int i = 1; i < tmp; i++) { cnt++; x[cnt] = querylca(x[i], x[i + 1]); } std::sort(x + 1, x + cnt + 1, comp); cnt = std::unique(x + 1, x + cnt + 1) - x - 1; top = 1; stack[top] = x[1]; for (int i = 2; i <= cnt; i++) { while (top > 0 && stack[top] != querylca(stack[top], x[i])) { top--; } if (stack[top]) { add(stack[top], x[i]); } top++; stack[top] = x[i]; } //calc ans for (int i = 1; i <= tmp - 1; i++) { flag[cc[i]] = 0; } edgenum = 0; for (int i = 1; i <= cnt; i++) { head[x[i]] = 0; } |
虚树