制作电子商务网站页面,搜索引擎最佳化,浦城 建网站,徐州集团网站建设公司虚树 问题引入
在一类树上动态规划问题中,题目给出的询问往往包含树上的很多各节点,并保证总的点数规模小于某个值.
如果我们直接在整颗树上进行dpdp的话,时间复杂度与询问的次数有关,这显然是不可接受的,如果我们可以找到一种动态规划的方法,使其时间复杂度与询问中点的实际…虚树 问题引入
在一类树上动态规划问题中,题目给出的询问往往包含树上的很多各节点,并保证总的点数规模小于某个值.
如果我们直接在整颗树上进行dpdpdp的话,时间复杂度与询问的次数有关,这显然是不可接受的,如果我们可以找到一种动态规划的方法,使其时间复杂度与询问中点的实际规模相关就好了.
于是虚树应运而生.
虚树概念
虚树即是一颗虚拟构建的一棵树,这个树只包含关键点以及关键lcalcalca的点,而其他不影响虚树结构的点和边都相当于进行了路径压缩,整颗虚树的规模不会超过关键点关键点关键点数目的两倍.
举个栗子
原树 虚树
包含关键点 1 2 3的虚树 包含关键点 1 3 7 8 的虚树 其中6是关键lcalcalca节点
很显然,其他不是那么关键的点及边形成的路径我们都将他们压缩到了一条边,例如在第二个虚树中,我们相当于把1−61−61-6的路劲压缩到了边1−61−61-6中,而999号节点这种非关键点我们直接扔掉了,因为我们在dp" role="presentation" style="position: relative;">dpdpdp的时候不会用到999号点.虚树构建预处理我们对整颗树得到dfs序列(即前序遍历),记为dfn[u]" role="presentation" style="position: relative;">dfn[u]dfn[u]dfn[u].
我们使用一个栈,从栈顶到栈底的元素形成虚树的一颗树链.
当我们得到一些询问点(关键点)的时候,对这些点按照他们的dfn[u]dfn[u]dfn[u]值进行排序,然后从dfndfndfn值小的开始扫描,结合栈中保存的树链信息就可以将这颗虚树构建出来.
假设我们当前扫到的关键点为uuu,栈指针为top" role="presentation" style="position: relative;">toptoptop,栈为stkstkstk. 1.如果栈为空,或者栈中只有一个元素,那么显然应该: stk[top]u;stk[top]u;stk[++top] = u; 2.取lcaLCA(u,stk[top])lcaLCA(u,stk[top])lca = LCA(u,stk[top]),如果lcastk[top]lcastk[top]lca = stk[top],则说明uuu点应该接着stk[top]" role="presentation" style="position: relative;">stk[top]stk[top]stk[top]点延长当前的树链.做操作: stk[top]u;stk[top]u;stk[++top] = u; 3.如果lca≠stk[top]lca≠stk[top]lca \ne stk[top],则说明uuu与stk[top]" role="presentation" style="position: relative;">stk[top]stk[top]stk[top]分属lcalcalca的两颗不同的子树,且包含stk[top]stk[top]stk[top]的这颗子树应该已经构建完成了,我们需要做的是: 将lcalcalca的包含stk[top]stk[top]stk[top]子树的那部分退栈,并将这部分建边形成虚树.如果lcalcalca不在栈(树链)中,那么要把lcalcalca也加入栈中,保证虚树的结构不出现问题,随后将uuu加入栈中,以表延长树链.
代码实现//实现逐个将关键点插入形成一颗虚树
void insert(int u){if(top = 1) {stk[++top] = u;return ;}int lca = LCA(u,stk[top]);if(lca == stk[top]) {stk[++top] = u;return ;}while(top 1 dfn[lca] = stk[top-1]) {addedge(stk[top-1],stk[top]);--top;}if(lca != stk[top]) stk[++top] = lca;stk[++top] = u;
}虚树例题[SDOI2011]消耗战题意给出n" role="presentation" style="position: relative;">nnn个点的一棵带有边权的树,以及qqq个询问.每次询问给出k" role="presentation" style="position: relative;">kkk个点,询问这使得这kkk个点与1" role="presentation" style="position: relative;">111点不连通所需切断的边的边权和最小是多少. 题解 令dp[n]dp[n]dp[n]表示从nnn开始不能到达其子树中的关键点所需切断的最小边权和.令me[u]" role="presentation" style="position: relative;">me[u]me[u]me[u]表示切断111到u" role="presentation" style="position: relative;">uuu的路径中的边权最小值. 设vvv是u" role="presentation" style="position: relative;">uuu的直接儿子. 如果vvv是关键节点,那么dp[u]+=me[v][1]" role="presentation" style="position: relative;">dp[u]+=me[v][1]dp[u]+=me[v][1]dp[u] += me[v]^{[1]},否则dp[u]min(me[v],dp[v])[2]dp[u]min(me[v],dp[v])[2]dp[u] += min(me[v],dp[v])^{[2]} (第[2][2][2]个转移方程的解释:要么直接切断1−v1−v1-v的路径,要么使得从vvv出发不能到达其子树的关键点.)显然我们不能针对每个询问对整颗子树进行dp" role="presentation" style="position: relative;">dpdpdp,时间复杂度过高,而我们发现那些非关键点我们没有必要在dpdpdp的时候考虑,所以使用虚树. 代码 const int maxn 250007;
const int inf 1e9;
vectorint RG[maxn],VG[maxn];
int U[maxn],V[maxn],C[maxn];
int dfn[maxn],deep[maxn];ll me[maxn];int fa[maxn][20];
int stk[maxn],top;
int n,m,idx;
void dfs(int u){dfn[u] idx;deep[u] deep[fa[u][0]] 1;for(int e : RG[u]){int v U[e] ^ V[e] ^ u;if(v fa[u][0]) continue;me[v] C[e];if(u ! 1 me[u] me[v]) me[v] me[u];fa[v][0] u;dfs(v);}
}int LCA(int u,int v){if(deep[u] deep[v]) swap(u,v);int delta deep[u] - deep[v];for(int i 19;i 0;--i){if((delta i) 1) u fa[u][i];}for(int i 19;i 0;--i){if(fa[u][i] ! fa[v][i]) u fa[u][i],v fa[v][i];}if(u v) return u;return fa[u][0];
}bool comp(int a,int b){return dfn[a] dfn[b];
}void insert(int u){if(top 1) {stk[top] u;return;}int lca LCA(u,stk[top]);if(lca stk[top]) {stk[top] u;return ;}while(top 1 dfn[lca] dfn[stk[top-1]]){VG[stk[top-1]].push_back(stk[top]);--top;}if(lca ! stk[top]) {VG[lca].push_back(stk[top]);stk[top] lca;} stk[top] u;
}int idq[maxn],mark[maxn];ll DP(int u){ll cost 0;for(int v : VG[u]){cost min(me[v],DP(v));}VG[u].clear();if(mark[u]) return me[u];else return cost;
}int main(){init();ios::sync_with_stdio(false);cin n;for(int i 1;i n;i){cin U[i] V[i] C[i];RG[U[i]].push_back(i);RG[V[i]].push_back(i);}dfs(1);for(int t 1;t 19;t) for(int i 1;i n;i){fa[i][t] fa[fa[i][t-1]][t-1];}cin m;for(int i 0;i m;i){int sz;cin sz;for(int j 0;j sz;j){cin idq[j];mark[idq[j]] 1;}sort(idq,idqsz,comp);top 0;stk[top] 1;for(int j 0;j sz;j) insert(idq[j]);while(top 0) {VG[stk[top-1]].push_back(stk[top]);top--;}cout DP(1) endl;for(int j 0;j sz;j) VG[idq[j]].clear(),mark[idq[j]] 0;VG[0].clear();}return 0;
}
