当前位置：首页 > news >正文

厦门专业网站设计公微信推广平台

news 2026/4/8 10:18:25

厦门专业网站设计公,微信推广平台,重庆建工网,公司招聘网站排行榜适用于解决一棵树中只需要用到少部分点的时候，将需要用到的点提出来单独建一棵树 /********************* 虚树 *********************/ struct edge {int to, next;int val; };struct Virtual_Tree {int n; // 点数int dfn[N]; // dfs序int dep[N]; // 深度int fa…

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

/********************* 虚树 *********************/
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;
/***********************************************/