【图论】虚树 - 模板总结

适用于解决一棵树中只需要用到少部分点的时候，将需要用到的点提出来单独建一棵树

/********************* 虚树 *********************/
struct edge
{int to, next;int val;
};struct Virtual_Tree
{int n; // 点数int dfn[N]; // dfs序int dep[N]; // 深度int fa[N][25], m[N];int num; // 关键点数vector<int> lst; // 关键点bool query[N]; // 是否为关键点int top, cnt1 = 1, cnt2 = 1, dfscnt = 1;int stk[MAXN];int head1[N], head2[N];struct edge edge1[N << 1], edge2[N << 1]; // 原树和虚树/* 在下方添加需要的信息定义 */int minv[N];/***************************/// 初始化void init(){for (int i = 1; i <= n; i ++ ){dfn[i] = dep[i] = m[i] = query[i] = 0;for (int j = 0; j < 24; j ++ ) fa[i][j] = 0;}}// 原树建边void add1(int x, int y, int v){edge1[cnt1].next = head1[x];edge1[cnt1].to = y;edge1[cnt1].val = v;head1[x] = cnt1 ++ ;}// 虚树建边void add2(int x, int y){edge2[cnt2].next = head2[x];edge2[cnt2].to = y;head2[x] = cnt2 ++ ;}// 预处理原树基本信息void dfs1(int pos){int k;for (k = 0; fa[pos][k]; k ++ ) fa[pos][k + 1] = fa[fa[pos][k]][k];m[pos] = k;dfn[pos] = dfscnt++;for (int i = head1[pos]; i; i = edge1[i].next){int to = edge1[i].to;if (!dfn[to]){dep[to] = dep[pos] + 1;fa[to][0] = pos;/* 在下方处理需要的信息 */minv[to] = min(minv[pos], edge1[i].val);/***********************/dfs1(to);}}}// 倍增求lcaint lca(int x, int y){if (dep[x] < dep[y]) swap(x, y);for (int i = m[x]; i > -1; i -- ){if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];}if (x == y) return x;for (int i = m[x]; i > -1; i -- ){if (fa[x][i] != fa[y][i]){x = fa[x][i];y = fa[y][i];}}return fa[x][0];}// 建虚树 关键点存在lst里 lst大小为k 下标从0开始void build(int k, vector<int>& lst){// 按照dfs序排序规则auto cmp = [&](int x1, int x2){return dfn[x1] < dfn[x2];};sort(lst.begin(), lst.end(), cmp);stk[top = 1] = lst[0];for (int i = 1; i < k; i ++ ){int now = lst[i];int lc = lca(now, stk[top]);while (1){if (dep[lc] >= dep[stk[top - 1]]){if (lc != stk[top]){add2(lc, stk[top]);if (lc != stk[top - 1]) stk[top] = lc;else top -- ;}break;}else{add2(stk[top - 1], stk[top]);top -- ;}}stk[++ top] = now;}while (-- top) add2(stk[top], stk[top + 1]);}// 树形dp计算答案int dfs2(int u){/* 下方填写计算答案代码逻辑 *//**************************/// 清空虚树query[u] = false;head2[u] = 0;return res;}// 在下方填写解题逻辑void solve(){/* 思路 *//********/// 每次建虚树后需要清空cnt2 = 1;lst.clear();}
} vtr;
/***********************************************/