虚树

一点理解

将关键点按dfs序排序后，所有关键点与相邻关键点的lca合起来构成虚树（通常还要加上整棵树的根）。 虚树至多有 2k 2 k 个点。体现在实现中就是每次都pop若干点，并有机会push2个点。

stk[]中存的是从根到当前点的递归栈中目前选入虚树的点。 stk中的点之间都未连边（因为事实上关系还未确定），pop掉一个点的同时把它的父边连上。

插入一个点时，计算这个点与上一个点的LCA，然后分类讨论：

当前点是上一个的子节点，直接把自己push进去否则根据top-1判断是否弹出top，直到出现第3类情况（top-1的深度 > > <script type="math/tex" id="MathJax-Element-42">></script>LCA的深度）a. 需要pop当前栈顶并push LCA，注意LCA是刚弹出的点的父亲 b. LCA就是当前栈顶，通常不需要做什么 然后把自己push进去

初始时，栈中包含{root, a[0]}（硬点a[0]），然后依次加入a[1]到a[n-1]。 root前面还要添加保护节点stk[0] = 0，并设置dep[0] = 0, dep[root] = 1，避免在栈中只有一个root时过度弹栈。

代码实现模板

Initialization：dfs处理in[MAXN], dep[MAXN]，查lca用的ST表以及adde时要用的一些信息

int a[MAXN], stk[MAXN] = {0,1}; inline bool cmp(int u, int v) {return in[u] < in[v];} void rebuild(int k) { for (int i = 0; i < k; i++) scanf("%d",a+i); sort(a, a+k, cmp); int *top = stk + 2; *top = a[0]; for (int i = 1; i < k; i++) { int f = lca(a[i],*top); //seems (*top == a[i-1]) //if (f == *top) case 1 while (dep[*(top-1)] >= dep[f]) //case 2: more to pop adde(*top, *(top-1)), top--; if (*top != f) //case 3a: pop top & push f adde(*top, f), *top = f; //f is ancestor of *top //else case 3b: usually nothing to do *++top = a[i]; //push itself } do adde(*top, *(top-1)); while (--top > stk + 1); //clear stack (don't forget!) }

虚树上dp时，可以直接在栈中记录dp值，因为stk本身就是虚树上dfs的递归栈。 把adde换成pushup即可。注意栈中的儿子还未向父亲pushup，弹栈时才pushup。

val_t solve(int k) { for (int i = 0; i < k; i++) scanf("%d",a+i); sort(a, a+k, cmp); int top = 2; dp[1].init(); //don't forget reinitialize dp[2].init( stk[2] = a[0] ); for (int i = 1; i < k; i++) { int f = lca(a[i],stk[top]); //seems (stk[top] == a[i-1]) //if (f == stk[top]) case 1 while (dep[stk[top-1]] >= dep[f]) //case 2: more to pop dp[top-1].pushup( dp[top].finish() ), top--; if (stk[top] != f) //case 3a: pop top & push f dp[top].upgrade( stk[top] = f ); //else case 3b: usually nothing to do stk[++top] = a[i]; //push itself dp[top].init(a[i]); } do dp[top-1].pushup( dp[top].finish() ); while (--top > 1); //clear stack (don't forget!) return dp[1].finish(); }

为了演示如何将树形dp改写为栈中dp，约定树形dp采用如下模板形式

class val_t; class dp_t { //demon class type public: void init(); //non-key point void init(int u); //key point val_t finish(); //self-process void pushup(val_t son); //pushup from val of son void upgrade(int fa); //inherit & pushup to fa } dp[MAXN]; void dp_t::upgrade(int fa) { //universal demon definition dp[fa].init(); dp[fa].pushup( finish() ); *this = dp[fa]; } val_t dfs(int x) { if (key[x]) dp[x].init(x); else dp[x].init(); for (int u : son[x]) dp[x].pushup( dfs(u) ); return dp[x].finish(); }