虚树笔记

Def

实际上就是把关键点和相关需要的信息拎出来。。。减少冗余的点。使得图中非关键点尽量少
前提在于非关键点可以用某种方法排除对结果的影响。

Met

随便抓一个点当根(一般情况下)
按dfs序递增排序
维护一个栈表示最右链(当前子树)
设当前插入点cur与栈顶点x的lca为anc
设栈里面的下一个元素为pre
看cur是不是在x的子树内。如果不在那就把x的子树都merge起来直到cur在栈顶的子树里然后推入栈
怎么merge呢QAQ?
- 如果pre是lca或在它上面儿(不在lca的子树内或者pre == lca
就x和lca连个边然后退栈
然后看退栈之前的pre是否是lca,如果不是lca记得把lca推进栈,
- 如果pre在子树里,就把x和pre连起来
把cur推入栈的时候别忘了判是否已经被当成原来的lca推进去了。
循环完之后别忘了把栈里的最右链连上边
以及上面在判各种东西的时候不用判dfn。。直接判dep就好了QAQ。。因为排完序了

具体看代码吧。
一开始窝第一遍写的时候漏洞百出。。。。最后还是看了网上的代码。。。
不过还是觉得这个写法好奇怪。。但是网上又看不到别的写法。。
就是这样QAQ。

SRC

    stk[++ t] = 1;
    for(int i = 1; i <= tot; ++ i){  
        int cur = a[i],tmp = lca(cur, stk[t]);  
        for(; ; ){  
            if(dep[tmp] >= dep[stk[t - 1]]){  
                add(tmp, stk[t --]);  
                if(tmp != stk[t]) stk[++ t] = tmp;  
                break;  
            }  
            add(stk[t - 1], stk[t]), -- t;  
        }  
        if(stk[t] != cur) stk[++ t] = cur;  
    }  
    REP(i, 1, t - 1) add(stk[i], stk[i + 1]);

bzoj2286这个题连边的时候记得判自环