• 虚树学习笔记

    1将一颗大树浓缩成小树，因为在一棵树中，有些信息是不必要的，只需要关注那些关键信息，保留原有的父子关系，从而方便树形dp之类的信息维护，降低时间复杂度。

    2建立虚树需要以下操作：

    （1）进行一次dfs，将关键点（涉及到询问的点）按照dfs序进行排序。

    （2）创建一个栈，起初栈只有一个根节点，这里需要用栈来保证栈中元素形成了一条链

    （3）关键点依次插入栈中，获取当前点和栈顶元素的lca，一开始放入栈中元素的规律是从上到下形成一条链，当出现一个不在这条链上的关键点是，这个点和当前栈顶的点（就是当前链的最末端）的lca必定在这条链上，从末端沿着向上找到lca所处的位置，（dfn[top-1]

    （4）因此，虚树虚树中保存的就是栈顶与关键点的lca以及关键点。

    代码实现：

    按照模板题：[SDOI2011] 消耗战 - 洛谷

    思路：用倍增法计算lca，同时根据倍增思想保存u到达往上2^i经过的边的最小值，根据最小边权进行虚树创建，最后进行dp

    1数据存储

    1. const int maxn=2e5+5e4+10;
    2. const int inf=0x3f3f3f3f;
    3. struct edge{
    4. 	int to;
    5. 	ll w;
    6. };
    7. vectorvv[maxn];//记录树 
    8. vectorvec[maxn];//记录虚树 
    9. int stk[maxn],top;//模拟栈 
    10. int dfn[maxn],cnt;
    11. int n,dep[maxn],fa[maxn][30];
    12. ll dis[maxn][22];//记录u点往上2^j的祖先节点这段路径中最小的边权 
    13. int q[maxn],m;//关键点 
    14. ll dp[maxn];
    15. bool vis[maxn];//标记关键点 
    16. int root=1;//树的根节点

     2第一次dfs，获取dfs序，向上2^0的父节点及最小边权，深度

    1. void dfs1(int u,int fat)//获取dfs序，父节点，以及通往父节点线段的长度 
    2. {
    3. 	dfn[u]=++cnt;
    4. 	fa[u][0]=fat;
    5. 	dep[u]=dep[fat]+1;
    6. 	for(edge p:vv[u])
    7. 	{
    8. 		int to=p.to;
    9. 		int w=p.w;
    10. 		if(fat==to)
    11. 		continue;
    12. 		dis[to][0]=p.w;
    13. 		dfs1(to,u);
    14. 	}
    15. }

    3预处理倍增所用的数组

    1. void pre_work()//预处理祖先节点和路径最小线段 
    2. {
    3. 	for(int j=1;j<=17;j++)
    4. 	for(int i=1;i<=n;i++)
    5. 	{
    6. 	fa[i][j]=fa[fa[i][j-1]][j-1];
    7. 	dis[i][j]=min(dis[i][j-1],dis[fa[i][j-1]][j-1]);	
    8. 	}
    9. }

    4在建虚树过程中，获取两点之间的边权

    1. ll query(int u,int v)//获取uv之间的路径 
    2. {
    3. 	ll ans=inf;
    4. 	for(int i=17;i>=0;i--)//u从下往上倍增往上爬 
    5. 	{
    6. 		if(fa[u][i]&&dep[fa[u][i]]>=dep[v])
    7. 		{
    8. 			ans=min(ans,dis[u][i]);//寻找其中最短路径 
    9. 			u=fa[u][i];
    10. 		}
    11. 	}
    12. 	return ans;
    13. }

     5建边（原本的数，虚树）

    1. inline void add1(int u,int v,int w)//添加树的边 
    2. {
    3. 	vv[u].push_back({v,w});
    4. 	vv[v].push_back({u,w});
    5. }
    6. inline void add2(int u,int v)//添加虚树的边 
    7. {
    8. 	ll w=query(v,u);
    9. 	vec[u].push_back({v,w});
    10. }

    6构建虚树

    1. bool cmp(const int &a,const int &b)//按照dfs序排序 
    2. {
    3. 	return dfn[a]
    4. }
    5. void insert(int u)
    6. {
    7. 	if(u==1)
    8. 	return; 
    9. 	int l=lca(u,stk[top]);
    10. 	while(top>1&&dfn[stk[top-1]]>=dfn[l])//寻找dfn[top-1]
    11. 	{
    12. 	add2(stk[top-1],stk[top]);
    13. 	top--;	
    14. 	}
    15. 	if(stk[top]!=l)//如果顶端不是lca，那么说明lca不存在，就插入栈中 
    16. 	{
    17. 		add2(l,stk[top]);
    18. 		stk[top]=l;
    19. 	}
    20. 	stk[++top]=u;
    21. }
    22. inline void build()
    23. {	
    24. 	sort(q+1,q+1+m,cmp);
    25. 	top=0;
    26. 	stk[++top]=root;
    27. 	for(int i=1;i<=m;i++)
    28. 	insert(q[i]);
    29. 	while(top>1)//将最后一条链加入虚树中 
    30. 	{
    31. 	add2(stk[top-1],stk[top]);
    32. 	top--;	
    33. 	}
    34. }

    7第二次dfs，进行树形dp

    1. void dfs2(int u)
    2. {
    3. 	for(int i=0;isize();i++) 
    4. 	{
    5. 		edge p=vec[u][i];
    6. 		int to=p.to;
    7. 		ll w=p.w;
    8. 		dfs2(to);
    9. 		if(vis[to])//如果to为关键点，这条边必须切断 
    10. 		dp[u]+=w;
    11. 		else
    12. 		dp[u]+=min(w,dp[to]);//如果不是关键点，可以切断to需要切断的或者直接切断to这条路径 
    13. 		vis[to]=0;
    14. 		dp[to]=0;	
    15. 	}
    16. 	vec[u].clear();	
    17. }

    8主函数

    1. int main(){
    2. 	cin>>n;
    3. 	for(int i=1;i
    4. 	{
    5. 		int u,v,w;
    6. 		cin>>u>>v>>w;
    7. 		add1(u,v,w);
    8. 	}
    9. 	dfs1(root,0);
    10. 	pre_work();
    11. 	int t;
    12. 	cin>>t;
    13. 	while(t--)
    14. 	{
    15. 		cin>>m;
    16. 		for(int i=1;i<=m;i++)
    17. 		{
    18. 			cin>>q[i];
    19. 			vis[q[i]]=1;
    20. 		}
    21. 		build();
    22. 		dfs2(root);
    23. 		cout<1]<<'\n';
    24. 		dp[1]=0;
    25. 	}
    26. 	return 0;
    27. }

    9完整代码

    1. #include 
    2. #define ll long long
    3. #define IOS ios::sync_with_stdio(false);cin.tie(0)
    4. using namespace std;
    5. const int maxn=2e5+5e4+10;
    6. const int inf=0x3f3f3f3f;
    7. struct edge{
    8. 	int to;
    9. 	ll w;
    10. };
    11. vectorvv[maxn];//记录树 
    12. vectorvec[maxn];//记录虚树 
    13. int stk[maxn],top;//模拟栈 
    14. int dfn[maxn],cnt;
    15. int n,dep[maxn],fa[maxn][30];
    16. ll dis[maxn][22];//记录u点往上2^j的祖先节点这段路径中最小的边权 
    17. int q[maxn],m;//关键点 
    18. ll dp[maxn];
    19. bool vis[maxn];//标记关键点 
    20. int root=1;//树的根节点 
    21. ll query(int u,int v)//获取uv之间的路径 
    22. {
    23. 	ll ans=inf;
    24. 	for(int i=17;i>=0;i--)//u从下往上倍增往上爬 
    25. 	{
    26. 		if(fa[u][i]&&dep[fa[u][i]]>=dep[v])
    27. 		{
    28. 			ans=min(ans,dis[u][i]);//寻找其中最短路径 
    29. 			u=fa[u][i];
    30. 		}
    31. 	}
    32. 	return ans;
    33. }
    34. inline void add1(int u,int v,int w)//添加树的边 
    35. {
    36. 	vv[u].push_back({v,w});
    37. 	vv[v].push_back({u,w});
    38. }
    39. inline void add2(int u,int v)//添加虚树的边 
    40. {
    41. 	ll w=query(v,u);
    42. 	vec[u].push_back({v,w});
    43. }
    44. void pre_work()//预处理祖先节点和路径最小线段 
    45. {
    46. 	for(int j=1;j<=17;j++)
    47. 	for(int i=1;i<=n;i++)
    48. 	{
    49. 	fa[i][j]=fa[fa[i][j-1]][j-1];
    50. 	dis[i][j]=min(dis[i][j-1],dis[fa[i][j-1]][j-1]);	
    51. 	}
    52. } 
    53. int lca(int x,int y)//获取最近公共祖先 
    54. {
    55. 	if(x==y)
    56. 	return x;
    57. 	if(dep[x]
    58. 	swap(x,y);
    59. 	for(int i=17;i>=0;i--)
    60. 	if(fa[x][i]&&dep[fa[x][i]]>=dep[y])
    61. 	x=fa[x][i];
    62. 	if(x==y)
    63. 	return x;
    64. 	for(int i=17;i>=0;i--)
    65. 	{
    66. 		if(fa[x][i]&&fa[y][i]&&fa[x][i]!=fa[y][i])
    67. 		{
    68. 			x=fa[x][i];
    69. 			y=fa[y][i];
    70. 		}
    71. 	}
    72. 	return fa[x][0];
    73. }
    74. void dfs1(int u,int fat)//获取dfs序，父节点，以及通往父节点线段的长度 
    75. {
    76. 	dfn[u]=++cnt;
    77. 	fa[u][0]=fat;
    78. 	dep[u]=dep[fat]+1;
    79. 	for(edge p:vv[u])
    80. 	{
    81. 		int to=p.to;
    82. 		int w=p.w;
    83. 		if(fat==to)
    84. 		continue;
    85. 		dis[to][0]=p.w;
    86. 		dfs1(to,u);
    87. 	}
    88. }
    89. void dfs2(int u)
    90. {
    91. 	for(int i=0;isize();i++) 
    92. 	{
    93. 		edge p=vec[u][i];
    94. 		int to=p.to;
    95. 		ll w=p.w;
    96. 		dfs2(to);
    97. 		if(vis[to])//如果to为关键点，这条边必须切断 
    98. 		dp[u]+=w;
    99. 		else
    100. 		dp[u]+=min(w,dp[to]);//如果不是关键点，可以切断to需要切断的或者直接切断to这条路径 
    101. 		vis[to]=0;
    102. 		dp[to]=0;	
    103. 	}
    104. 	vec[u].clear();	
    105. } 
    106. bool cmp(const int &a,const int &b)//按照dfs序排序 
    107. {
    108. 	return dfn[a]
    109. }
    110. void insert(int u)
    111. {
    112. 	if(u==1)
    113. 	return; 
    114. 	int l=lca(u,stk[top]);
    115. 	while(top>1&&dfn[stk[top-1]]>=dfn[l])//寻找dfn[top-1]
    116. 	{
    117. 	add2(stk[top-1],stk[top]);
    118. 	top--;	
    119. 	}
    120. 	if(stk[top]!=l)//如果顶端不是lca，那么说明lca不存在，就插入栈中 
    121. 	{
    122. 		add2(l,stk[top]);
    123. 		stk[top]=l;
    124. 	}
    125. 	stk[++top]=u;
    126. }
    127. inline void build()
    128. {	
    129. 	sort(q+1,q+1+m,cmp);
    130. 	top=0;
    131. 	stk[++top]=root;
    132. 	for(int i=1;i<=m;i++)
    133. 	insert(q[i]);
    134. 	while(top>1)//将最后一条链加入虚树中 
    135. 	{
    136. 	add2(stk[top-1],stk[top]);
    137. 	top--;	
    138. 	}
    139. }
    140. int main(){
    141. 	cin>>n;
    142. 	for(int i=1;i
    143. 	{
    144. 		int u,v,w;
    145. 		cin>>u>>v>>w;
    146. 		add1(u,v,w);
    147. 	}
    148. 	dfs1(root,0);
    149. 	pre_work();
    150. 	int t;
    151. 	cin>>t;
    152. 	while(t--)
    153. 	{
    154. 		cin>>m;
    155. 		for(int i=1;i<=m;i++)
    156. 		{
    157. 			cin>>q[i];
    158. 			vis[q[i]]=1;
    159. 		}
    160. 		build();
    161. 		dfs2(root);
    162. 		cout<1]<<'\n';
    163. 		dp[1]=0;
    164. 	}
    165. 	return 0;
    166. }

  • 相关阅读:
    图扑数字孪生智慧加油站，构建安全防护网
    C++ string常用函数用法总结
    QT+OSG/osgEarth编译之四十四：osgText+Qt编译（一套代码、一套框架，跨平台编译，版本：OSG-3.6.5工具库osgText）
    16_开发工具IntelliJ IDEA
    Visual Studio 2022 设置 PySide6 扩展工具
    动态内存与智能指针
    Shell开发实践：服务器的磁盘、CPU、内存的占用监控
    医疗IT系统安科瑞隔离电源装置在医院的应用
    聚类算法模型评价指标
    【等保小知识】等级保护单项测评包括哪些项目？
  • 原文地址：https://blog.csdn.net/m0_63737271/article/details/125899654