適用于解決一棵樹中只需要用到少部分點(diǎn)的時(shí)候，將需要用到的點(diǎn)提出來單獨(dú)建一棵樹

/********************* 虛樹 *********************/
struct edge
{int to, next;int val;
};struct Virtual_Tree
{int n; // 點(diǎn)數(shù)int dfn[N]; // dfs序int dep[N]; // 深度int fa[N][25], m[N];int num; // 關(guān)鍵點(diǎn)數(shù)vector<int> lst; // 關(guān)鍵點(diǎn)bool query[N]; // 是否為關(guān)鍵點(diǎ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 ++ ;}// 預(yù)處理原樹基本信息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];}// 建虛樹 關(guān)鍵點(diǎn)存在lst里 lst大小為k 下標(biāo)從0開始void build(int k, vector<int>& lst){// 按照dfs序排序規(guī)則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計(jì)算答案int dfs2(int u){/* 下方填寫計(jì)算答案代碼邏輯 *//**************************/// 清空虛樹query[u] = false;head2[u] = 0;return res;}// 在下方填寫解題邏輯void solve(){/* 思路 *//********/// 每次建虛樹后需要清空cnt2 = 1;lst.clear();}
} vtr;
/***********************************************/