首页 > 其他分享 >【树】虚树

【树】虚树

时间：2023-01-27 18:55:57浏览次数：49  
标签：sta int top lca 虚树 dp add2

基本概念

有一类题，给出了一棵树后需要进行多次以其中某些不同节点为重要节点的树形dp
针对这类题我们会发现有大量冗余的点不需要进行任何转移，只需要进行向上或向下转移就可以
此时我们就可以直接将这些点初始化出来，重新建棵树，这就是虚树。

工作原理

主要利用单调栈工作 比较套路 具体思想看注释
\(a[i]\)表示第i个重要节点、edge2存储虚树图

inline bool cmp(int x , int y){
	return dfn[x] < dfn[y] ;
}

inline void build(int rt , int k){
	sort(a+1 , a+1+k , cmp) ;//按照dfs序排序，防止祖先后代顺序颠倒
	sta[1] = rt ;//初始化单调栈
	top = 1 ;
	edge_cnt2 = 1 ;
	for(int i = 1;i <= k;++i){
		if(a[i] == rt)	continue ;//一开始的1号节点是一定会放的，如果又遇到了就避免重复不放
		int lca = LCA(a[i] , sta[top]) ;
		if(sta[top] != lca){
			while(top >= 2 && dfn[lca] < dfn[sta[top-1]]){//一直出栈并建边直到lca的dfs序比栈顶下面的一个还大
				add2(sta[top] , sta[top-1]) ;
				add2(sta[top-1] , sta[top]) ;
				top-- ;
			}
			if(dfn[lca] > dfn[sta[top-1]]){//比较栈顶和lca的dfs序：lca不是栈顶
				add2(sta[top] , lca) ;
				add2(lca , sta[top]) ;
				sta[top] = lca ;//就放入栈
			}else{
				add2(sta[top] , lca) ;
				add2(lca , sta[top]) ;
				top-- ;//lca就是栈顶，直接建边出栈即可
			}
		}
		sta[++top] = a[i] ;//lca处理完，a[i]一定要入栈
	}
	for(int i = 1;i < top;++i){//给剩余的建边，他们是单独的另一条链
		add2(sta[i] , sta[i+1]) ;
		add2(sta[i+1] , sta[i]) ;
	}
}

oi-wiki可供参考

注意事项

· 大部分虚树题目的难点不在建树，而是在设计状态转移方程。
可以先考虑在原树上进行状态设计，后搬到虚树上
· 注意虚树上的边大都无边权，具体计算距离方式可使用\(\delta siz[]\)或插头dp
小心虚树题一般都是卡常题，如果清空重要节点标记时用\(memset()\)会TLE
用\(for\)循环

for(int i = 1;i <= k;++i)	check[a[i]] = false ;

· \(sort\)后的重要节点顺序不是原节点序 如果需要按节点顺序输出需要重新声明一个数组保存

例题引入

P2495 [SDOI2011] 消耗战

题目链接
比较模板 关键在于状态转移方程
找到两个关键节点之间的代价最小路径
\(minv[i]\)表示从根节点到第\(i\)号节点的最小代价路径
\(dp[i]\)表示根节点为\(i\)的子树的代价和为多少

code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std ;

const int MAXN = 6e5+10 ;

int n ,m ;
int head1[MAXN] ,head2[MAXN] ;
int edge_cnt1 = 1 ,edge_cnt2 = 1 ;
struct Edge{
	int to ,next ;
	int w ;
}edge1[MAXN<<1] ,edge2[MAXN<<1] ;
long long minv[MAXN] ;
int a[MAXN] ;

inline void add1(int from , int to , int w){
	edge1[edge_cnt1].to = to ;
	edge1[edge_cnt1].next = head1[from] ;
	edge1[edge_cnt1].w = w ;
	head1[from] = edge_cnt1++ ;
}

inline void add2(int from , int to){
	edge2[edge_cnt2].to = to ;
	edge2[edge_cnt2].next = head2[from] ;
	head2[from] = edge_cnt2++ ;
}

int dep[MAXN] ,fa[MAXN][35] ,dfn[MAXN] ;
int id = 0 ;
inline void dfs_init(int u , int f){
	dfn[u] = ++id ;
	for(int i = head1[u];i;i = edge1[i].next){
		int v = edge1[i].to ;int w = edge1[i].w ;
		if(v == f)	continue ;
		dep[v] = dep[u] + 1 ;
		fa[v][0] = u ;
		for(int j = 1;j <= 20;++j)
			fa[v][j] = fa[fa[v][j-1]][j-1] ;
		minv[v] = min(minv[u] , w*1ll) ;
		dfs_init(v , u) ;
	}
}

inline int LCA(int x , int y){
	if(dep[y] < dep[x])	swap(x , y) ;
	for(int i = 20;i >= 0;--i)
		if(dep[fa[y][i]] >= dep[x])
			y = fa[y][i] ;
	if(x == y)	return x ;
	for(int i = 20;i >= 0;--i)
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i] ;
			y = fa[y][i] ;
		}
	return fa[x][0] ;
}

inline bool cmp(int x , int y){
	return dfn[x] < dfn[y] ;
}

int sta[MAXN] ;
inline void build_tree(int rt , int k){
	sort(a+1 , a+1+k , cmp) ;
	int top = 1 ;
	edge_cnt2 = 1 ;
	sta[top] = rt ;
	
	for(int i = 1;i <= k;++i){
		if(a[i] == rt)	continue ;
		int lca = LCA(a[i] , sta[top]) ;
		if(lca != sta[top]){
			while(top >= 2 && dfn[lca] < dfn[sta[top - 1]]){
				add2(sta[top - 1] , sta[top]) ;
				add2(sta[top] , sta[top - 1]) ;
				top-- ;
			}
			if(dfn[lca] > dfn[sta[top - 1]]){
				add2(lca , sta[top]) ;
				add2(sta[top] , lca) ;
				sta[top] = lca ;
			}else{
				add2(lca , sta[top]) ;
				add2(sta[top] , lca) ;
				top-- ;
			}
		}
		sta[++top] = a[i] ;
	}
	for(int i = 1;i < top;++i)
		add2(sta[i] , sta[i + 1]) ,add2(sta[i + 1] , sta[i]) ;
}

long long dp[MAXN] ;
bool check[MAXN] ;
inline void treedp(int u , int f){
	dp[u] = 0 ;
	for(int i = head2[u];i;i = edge2[i].next){
		int v = edge2[i].to ;
		if(v == f)	continue ;
		treedp(v , u) ;
		if(check[v])
			dp[u] += minv[v] ;
		else
			dp[u] += min(minv[v] , dp[v]) ;
	}
	head2[u] = 0 ;
}

int main(){
	scanf("%d" , &n) ;
	for(int i = 1;i < n;++i){
		int u ,v ;int w ;
		scanf("%d%d%d" , &u , &v , &w) ;
		add1(u , v , w) ;
		add1(v , u , w) ;
	}
	
	memset(minv , 0x3f , sizeof minv) ;
	dep[1] = 1 ;
	fa[1][0] = 0 ;
	dfs_init(1 , -1) ;
	
	scanf("%d" , &m) ;
	while(m--){
		int k ;
		scanf("%d" , &k) ;
		for(int i = 1;i <= k;++i){
			scanf("%d" , a + i) ;
			check[a[i]] = true ;
		}
		
		build_tree(1 , k) ;
		
		treedp(1 , -1) ;
		
		printf("%lld\n" , dp[1]) ;
		
		for(int i = 1;i <= k;++i)	check[a[i]] = 0 ;
	}
	return 0 ;
}

P3233 [HNOI2014]世界树

题目链接
此题利用 插头dp 的思路
还是先想原树思路 后搬到虚树上
新的思考方式：将树上路径转化为欧几里得距离（？雾
有时间可以想想看

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;

const int MAXN = 5e5+10 ;

int n ,m ;
int head1[MAXN] ,head2[MAXN] ;
int edge_cnt1 = 1 ,edge_cnt2 = 1 ;
struct Edge{
	int to ,next ;
}edge1[MAXN << 1] ,edge2[MAXN << 1] ;

inline void add1 (int from , int to){
	edge1[edge_cnt1].to = to ;
	edge1[edge_cnt1].next = head1[from] ;
	head1[from] = edge_cnt1++ ;
}

inline void add2 (int from , int to){
	edge2[edge_cnt2].to = to ;
	edge2[edge_cnt2].next = head2[from] ;
	head2[from] = edge_cnt2++ ;
}

int dfn[MAXN] ,dep[MAXN] ,fa[MAXN][25] ,siz[MAXN] ,id = 0 ;
inline void dfs_init(int u , int f){
	dfn[u] = ++id ;
	siz[u] = 1 ;
	for(int i = head1[u];i;i = edge1[i].next){
		int v = edge1[i].to ;
		if(v == f)	continue ;
		fa[v][0] = u ;
		for(int j = 1;j <= 20;++j)	fa[v][j] = fa[fa[v][j-1]][j-1] ;
		dep[v] = dep[u] + 1 ;
		dfs_init(v , u) ;
		siz[u] += siz[v] ;
	}
}

inline int LCA(int x , int y){
	if(dep[x] > dep[y])	swap(x , y) ;
	for(int i = 20;i >= 0;--i)	if(dep[fa[y][i]] >= dep[x])	y = fa[y][i] ;
	if(x == y)	return x ;
	for(int i = 20;i >= 0;--i)
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i] ;
			y = fa[y][i] ;
		}
	return fa[x][0] ;
}

inline bool cmp(int x , int y){
	return dfn[x] < dfn[y] ;
}

bool check[MAXN] ;
int a[MAXN] ;
int sta[MAXN] ,top = 1 ;
inline void build(int rt , int k){
	sort(a+1 , a+1+k , cmp) ;
	sta[1] = rt ;
	top = 1 ;
	edge_cnt2 = 1 ;
	for(int i = 1;i <= k;++i){
		if(a[i] == rt)	continue ;
		int lca = LCA(a[i] , sta[top]) ;
		if(sta[top] != lca){
			while(top >= 2 && dfn[lca] < dfn[sta[top-1]]){
				add2(sta[top] , sta[top-1]) ;
				add2(sta[top-1] , sta[top]) ;
				top-- ;
			}
			if(dfn[lca] > dfn[sta[top-1]]){
				add2(sta[top] , lca) ;
				add2(lca , sta[top]) ;
				sta[top] = lca ;
			}else{
				add2(sta[top] , lca) ;
				add2(lca , sta[top]) ;
				top-- ;
			}
		}
		sta[++top] = a[i] ;
	}
	for(int i = 1;i < top;++i){
		add2(sta[i] , sta[i+1]) ;
		add2(sta[i+1] , sta[i]) ;
	}
}

int dp[MAXN] ,g[MAXN] ;//dp[]表示到最近的会议点的距离，g[]表示所属会议点
inline void dfs1(int u , int f){
	dp[u] = 0x3f3f3f3f ;
	for(int i = head2[u];i;i = edge2[i].next){
		int v = edge2[i].to ;
		if(v == f)	continue ;
		dfs1(v , u) ;
		int delta = dep[v] - dep[u] ;//虚树上的点在实树上不连续，计算边长
		if(dp[v] + delta < dp[u]){
			dp[u] = dp[v] + delta ;
			g[u] = g[v] ;
		}else if(dp[v] + delta == dp[u]){
			g[u] = min(g[u] , g[v]) ;//取最小编号
		}
	}
	if(check[u])	dp[u] = 0 ,g[u] = u ;
}

int ans[MAXN] ;
inline void cal(int x , int y){
	int p = y ,q = y ;//p是x点，q最终是分割点；dep[p] < dep[q] < dep[y]
	for(int i = 20;i >= 0;--i)
		if(dep[fa[p][i]] >= dep[x])
			p = fa[p][i] ;
	ans[g[x]] -= siz[p] ;//减去q对应上来的儿子：可以直接减去p枝后面再加上p到q之间的距离
	for(int i = 20;i >= 0;--i){//倍增找到分割点
		int llen = dep[y] - dep[fa[q][i]] + dp[y] ;//靠下位置
		int rlen = dep[fa[q][i]] - dep[x] + dp[x] ;//靠上位置
		if(dep[fa[q][i]] > dep[x] && (llen < rlen || (llen == rlen && g[y] < g[x])))
			q = fa[q][i] ;
	}
	ans[g[y]] += siz[q] - siz[y] ;//加上虚树边上其他的分支子树
	ans[g[x]] += siz[p] - siz[q] ;
}

inline void dfs2(int u , int f){
	for(int i = head2[u];i;i = edge2[i].next){
		int v = edge2[i].to ;
		if(v == f)	continue ;
		int delta = dep[v] - dep[u] ;
		if(dp[u] + delta < dp[v]){
			dp[v] = dp[u] + delta ;
			g[v] = g[u] ;
		}else if(dp[u] + delta == dp[v]){
			g[v] = min(g[u] , g[v]) ;
		}
		cal(u , v) ;//换根后才可以真正确定dp值，才可以计算贡献
		dfs2(v , u) ;
	}
	ans[g[u]] += siz[u] ;//自己子树（虚树）都属于这个会议点，如果子树上还有点前面已被减去
	head2[u] = 0 ;
}

int mem[MAXN] ;
int main(){
	scanf("%d" , &n) ;
	for(int i = 1;i < n;++i){
		int u ,v ;
		scanf("%d%d" , &u , &v) ;
		add1(u , v) ;
		add1(v , u) ;
	}
	dep[1] = 1 ;
	dfs_init(1 , -1) ;
	scanf("%d" , &m) ;
	while(m--){
		int k ;
		scanf("%d" , &k) ;
		for(int i = 1;i <= k;++i){
			scanf("%d" , a+i) ;
			check[a[i]] = true ;
			ans[a[i]] = 0 ;
			mem[i] = a[i] ;
		}
		build(1 , k) ;

		dfs1(1 , -1) ;
		dfs2(1 , -1) ;
		for(int i = 1;i <= k;++i)	printf("%d " , ans[mem[i]]) ;
		printf("\n") ;
		
		for(int i = 1;i <= k;++i)	check[a[i]] = false ;
	}
	
	return 0 ;
}

总结归纳

关键点在于树形dp掌握得如何
计算虚树上节点之间距离、节点与树外节点之间距离 很重要
需要多多思考 还有巨多细节

标签：sta,int,top,lca,虚树,dp,add2
From： https://www.cnblogs.com/adolf-stalin/p/17069158.html

相关文章

  • [虚树记录] CF613D Kingdom and its Cities
    这只蒟蒻看完题完全不会做，但是这只蒟蒻是通过百度搜索虚树找到这题的，发现这道CF*2800的题居然是许多人介绍虚树的第一道例题！我大概可以退役力！不过看完题解觉得真的还挺可......
  • 【XSY1976】【BZOJ2286】【SDOI2011】消耗战（虚树，dp）
    这题的dp思想还是比较容易想的，关键是如何保证时间复杂度，这时就用到了虚树的技巧。1.虚树是什么？（虚树的性质）不妨设现在询问给出了\(k\)个点，我们命名这些节点为关键节点。......
  • 虚树
    虚树我们有这样一类问题，对于一个有\(n\)个点的树，有\(m\)组询问，每次询问给出\(k\)个关键点，关键点之间的最短距离。其中\(\sumk\len,n\le1e5\)。我们发现这一类......
  • 虚树
    在给定树上给出一些关键点，要求构造一棵树，满足所有关键点都在这棵树上，且树的形态与关键点在原树上的形态不变：即本不是祖先/后辈关系的点成为祖先/后辈是不允许的，本来是祖先/......
  • 虚树
    前置知识：树的dfs序及其性质参考：洛谷日报定义某棵树\(T\)上存在一个关键点点集\(S\)。如果存在某个点集\(T'\)满足\(S\subseteqT'\subseteqT\)，且\(\forallu,......
  • 小学二年级都能看懂的 虚树学习笔记
    过不去那道题？事实：它数据范围很大而且每一次询问都得O(n)暴力出题人最坏了！介绍……虚树！介绍先看这么一道题P2495[SDOI2011]消耗战题目大意：每一次给k个特殊点，每次......
  • 虚树
    虚树是一种神奇的算法，它的具体思想为在一棵较为庞大的树当中，我们可能并不需要考虑该树上的所有节点，而是只需要考虑其中的一部分的话，我们可以使用这些点组建一棵虚树。虚树......
  • 虚树
    一种大树变小树的方法。大概就是只保留题目要求的关键点和其他一些统计答案必须的点，把剩余的所有点从树上砍掉。原理是维护一条最右链（就是我们扫到的最右边的一条链，它左边......
  • dfs序 括号序 欧拉序 树上莫队 虚树建立 傻傻分不清
    括号序进加一次，出加一次，显然最后得到的序列只有\(2n\)个点。voiddfs(intx){ in[x]=++tot; for(y)dfs(y); out[x]=++tot;}显然我们希求将树上路径表示为区......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99