【模板】【虚树】

 1 int build(){ // 虚树构建，pi存放关键点
 2 
 3     if(!sz(pi)) return 0;
 4     sort(pi.begin(), pi.end(), [](int x, int y){ return dfn[x] < dfn[y]; });
 5     // pi.erase(unique(pi.begin(), pi.end()), pi.end()); // 按需去重
 6     // for(auto &v : pi) tag[v] = 1; // 按需标记
 7     stk[top = 1] = pi[0];
 8     for(int i = 1; i < sz(pi); ++i){
 9 
10         int v = pi[i], lc = lca(stk[top], v);
11         while(dep[lc] < dep[stk[top - 1]]) P[stk[top - 1]].pb(stk[top]), --top;
12         if(lc != stk[top]){
13 
14             P[lc].pb(stk[top]), --top;
15             if(lc != stk[top]) stk[++top] = lc;
16         }
17         stk[++top] = v;
18     }
19     while(--top) P[stk[top]].pb(stk[top + 1]);
20     return stk[1];
21 }