首页 > 其他分享 >虚树学习笔记

虚树学习笔记

时间：2024-03-07 21:35:15浏览次数：33  
标签：特殊 int top 笔记 stk 学习 lca 节点 虚树

虚树学习笔记

定义

虚树指的是不同于原树（我称之为实树）的重构树，使得在同样能够求解的情况下，整棵树的节点数更少，从而使得在存在多次询问时，一些复杂度关于树的节点数的树上算法能够在时限内求解。

常用场景

一般来说，虚树的使用场景比较单一，常见于在实树上存在一些特殊节点，并且答案与这些节点有关的题目，此时可以提炼出所有特殊节点重新构建一棵树。

构造

首先将所有的特殊点提取出，然后按 dfn 序排序，接着依次放入栈中，同时判断连续两个特殊点 lca 的位置关系，维护一个最右链，使得栈内所有元素连起来是虚树中的一条链，栈顶元素一定是一个特殊点，所有 dfn 序比栈顶元素小，且不在栈内的元素都已经加入到虚树当中。具体过程如下。

在每一次添加新的特殊点之后，它和栈顶的特殊点的 lca 和栈顶的两个元素的位置关系可能有下面 \(4\) 种情况：

  1. 新的特殊点和栈顶的特殊点的 lca 就是栈顶的特殊点。此时，最右链从原来的 top-1->top 变为 top-1->top->new，因此只需要加入新的节点即可。
  2. 新的特殊点和栈顶的特殊点的 lca 在两个栈顶元素之间。此时，最右链从原来的 top-1->top 变为了 top-1->lca->new，因此将边 lca->top 加入虚树中，top 出栈，并且将 lca 和 new 依次加入栈中。
  3. 新的特殊点和栈顶的特殊点的 lca 是次栈顶元素。此时，最右链从原来的 top-1->top 变为了 top-1->new，因此将 top 出栈，再将 new 加入栈中。
  4. 新的特殊点和栈顶的特殊点的 lca 在次栈顶元素上。此时，最右链从原来的 top-n->top-n+1->...->top-1->top 变为了 top-n->lca->new。可以利用循环性质，每一次去除一条边，在不满足此性质后，一定属于情况 1,2,3 中任何一种可直接修改的情况。

code

scanf("%d",&k);
for(int i=1;i<=k;i++){
    scanf("%d",&lst[i]);
    ask[lst[i]]=true;
}
sort(lst+1,lst+1+k,cmp);
stk[top=1]=lst[1];
for(int i=2;i<=k;i++){
    int lc=lca(stk[top],lst[i]);
    while(1){
        if(Dep[lc]>=Dep[stk[top-1]]){
            if(lc!=stk[top]){
                add_edge1(lc,stk[top]);
                if(lc!=stk[top-1])stk[top]=lc;
                else --top;
            }
            break;
        }else{
            --top;
            add_edge1(stk[top],stk[top+1]);
        }
    }
    stk[++top]=lst[i];
}
while(--top)add_edge1(stk[top],stk[top+1]);

一些问题

Q：当栈内只有 \(1\) 个点时，也能够完成正确的操作吗？

A：可以。利用数组模拟栈，当 top=1 时，top-1 意味着未被赋值的 \(0\)，而 \(0\) 的深度为 \(0\)，意味着此时情况一定属于情况 1,2，则不会出现问题。但当栈内没有元素时会发生数组越界，因此需要将第一个特殊节点直接入栈。

Q：为什么要将特殊节点按 dfn 序排序？

A：若不按 dfn 序排序，则新的特殊节点可能在最右链的左边，此时会导致求解出现问题导致循环陷入死循环然后 MLE（关于我怎么知道会 MLE，详见例题-P687.[bzoj2286] [Sdoi2011]消耗战）。

Q：虚树的节点不会过多吗？

A： 不会。按照构造原理来说，每两个相邻的特殊的节点的 lca 也会加入虚树，最多 \(k-1\) 个，再加上原有的 \(k\) 个特殊节点，最差情况下共有 \(2k-1\) 个节点。

例题

P687. [bzoj2286] [Sdoi2011]消耗战

Solution1

看到题面，想到树形dp。考虑 \(f_i\) 表示为在节点 \(i\) 的子树内部所有的特殊节点都切断与 \(1\) 号节点连接的最小花费。当节点 \(i\) 不是特殊节点时可以把节点 \(i\) 和节点 \(1\) 切断连接，也可以把节点 \(i\) 子树内部所有的特殊节点和节点 \(i\) 切断连接。但当节点 \(i\) 是特殊节点时只能把节点 \(i\) 和节点 \(1\) 切断连接。复杂度为 \(O(nm)\)

Solution2

考虑到当一个子树内部完全没有特殊节点时该节点无用，而答案仅与 \(k\) 个特殊节点有关，因此可以利用虚树将树的节点数缩减至 \(2k-1\) 个，再按同样的思路跑一遍树形dp，复杂度 \(O(\sum k)\)

code
#include <bits/stdc++.h>
using namespace std;

const int N=2.5e5;
int n,m,k,u,v,w,cnt=1,cnt1,top,tot;
int head[N+5],to[(N<<1)+5],nxt[(N<<1)+5],dis[(N<<1)+5],head1[N+5],to1[N+5],nxt1[N+5],stk[N+5],Dep[N+5],Siz[N+5],Son[N+5],Top[N+5],Faz[N+5],Dfn[N+5],lst[N+5];
long long Min[N+5];
bool ask[N+5];

void add_edge(int u,int v,int w){
	to[cnt]=v,dis[cnt]=w,nxt[cnt]=head[u];
	head[u]=cnt++;
	return ;
}

void add_edge1(int u,int v){
	to1[cnt1]=v,nxt1[cnt1]=head1[u];
	head1[u]=cnt1++;
	return ;
}

bool cmp(int a,int b){
	return Dfn[a]<Dfn[b];
}

long long min(long long a,long long b){
	return a<b?a:b;
}

void dfs(int u,int f){
	Siz[u]=1,Son[u]=0;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i],w=dis[i];
		if(v==f)continue;
		Faz[v]=u,Dep[v]=Dep[u]+1,Min[v]=min(Min[u],w);
		dfs(v,u);
		Siz[u]+=Siz[v];
		if(Siz[v]>Siz[Son[u]])Son[u]=v;
	}
	return ;
}

void build(int u,int rt){
	Top[u]=rt,Dfn[u]=++tot;
	if(Son[u])build(Son[u],rt);
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==Faz[u]||v==Son[u])continue;
		build(v,v);
	}
}

int lca(int x,int y){
	while(Top[x]!=Top[y]){
		if(Dep[Top[x]]<=Dep[Top[y]])swap(x,y);
		x=Faz[Top[x]];
	}
	if(Dep[x]<Dep[y])swap(x,y);
	return y;
}

long long dfs1(int u){
	long long sum=0,res=0;
	for(int i=head1[u];i;i=nxt1[i]){
		int v=to1[i];
		sum+=dfs1(v);
	}
	if(ask[u])res=Min[u];
	else res=min(sum,Min[u]);
	ask[u]=false,head1[u]=0;
	return res;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w),add_edge(v,u,w);
	}
	Min[1]=1e18,Dep[1]=1;
	dfs(1,0);
	build(1,1);
	scanf("%d",&m);
	while(m--){
		cnt1=1;
		scanf("%d",&k);
		for(int i=1;i<=k;i++){
			scanf("%d",&lst[i]);
			ask[lst[i]]=true;
		}
		sort(lst+1,lst+1+k,cmp);
		stk[top=1]=lst[1];
		for(int i=2;i<=k;i++){
			int lc=lca(stk[top],lst[i]);
			while(1){
				if(Dep[lc]>=Dep[stk[top-1]]){
					if(lc!=stk[top]){
						add_edge1(lc,stk[top]);
						if(lc!=stk[top-1])stk[top]=lc;
						else --top;
					}
					break;
				}else{
					--top;
					add_edge1(stk[top],stk[top+1]);
				}
			}
			stk[++top]=lst[i];
		}
		while(--top)add_edge1(stk[top],stk[top+1]);
		printf("%lld\n",dfs1(stk[1]));
	}
	return 0;
}

Some saying

不必多言

P2014. 「SDOI2015」寻宝游戏

Solution1

考虑到最终的答案就是一个包含所有特殊节点的极小联通子树的边权和的二倍，而这个数值和按照 dfn 序排序后，任意两个相邻特殊节点的距离的和相等（首尾也算相邻）。因此添加一个节点 \(y\) 后，如果它左边的节点为 \(x\)，右边的节点为 \(z\)，那么答案就增加 \(dis(x,y)+dis(y,z)-dis(x,z)\)。删去一个节点则正相反，考虑用 set 可以简单维护。

code
#include <bits/stdc++.h>
using namespace std;

const int N=1e5;
int n,m,x,y,z,t,pre,nxt;
long long ans;
bool vis[N+5];
struct R_Graph{
	int cnt;
	int head[N+5],v[(N<<1)+5],to[(N<<1)+5],w[(N<<1)+5];
	void clear(){
		cnt=1;
		return ;
	}
	void add_edge(int x,int y,int z){
		v[cnt]=y,w[cnt]=z,to[cnt]=head[x];
		head[x]=cnt++;
		return ;
	}
}RG;
struct LCA{
	int tot;
	int dep[N+5],siz[N+5],son[N+5],faz[N+5],dfn[N+5],top[N+5],rk[N+5];
	long long dis[N+5];
	void dfs1(int u){
		siz[u]=1,son[u]=0;
		for(int i=RG.head[u];i;i=RG.to[i]){
			int v=RG.v[i],w=RG.w[i];
			if(v==faz[u])continue;
			dep[v]=dep[u]+1,faz[v]=u,dis[v]=dis[u]+w;
			dfs1(v);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
		return ;
	}
	void dfs2(int u,int rt){
		dfn[u]=++tot,top[u]=rt,rk[tot]=u;
		if(son[u])dfs2(son[u],rt);
		for(int i=RG.head[u];i;i=RG.to[i]){
			int v=RG.v[i];
			if(v==faz[u]||v==son[u])continue;
			dfs2(v,v);
		}
	}
	int lca(int x,int y){
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			x=faz[top[x]];
		}
		if(dep[x]<dep[y])swap(x,y);
		return y;
	}
	long long get_dis(int x,int y){
		return dis[x]+dis[y]-2*dis[lca(x,y)];
	}
}Lca;
set<int>s;
set<int>::iterator it;

int main(){
	RG.clear();
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		RG.add_edge(x,y,z),RG.add_edge(y,x,z);
	}
	Lca.dfs1(1),Lca.dfs2(1,1);
	for(int i=1;i<=m;i++){
		scanf("%d",&t);
		if(!vis[t])s.insert(Lca.dfn[t]);
		pre=Lca.rk[(it=s.lower_bound(Lca.dfn[t]))==s.begin()?*--s.end():*--it];
		nxt=Lca.rk[(it=s.upper_bound(Lca.dfn[t]))==s.end()?*s.begin():*it];
		if(vis[t])s.erase(Lca.dfn[t]);
		long long dis=Lca.get_dis(pre,t)+Lca.get_dis(t,nxt)-Lca.get_dis(pre,nxt);
		if(!vis[t]){
			vis[t]=true;
			ans+=dis;
		}else{
			vis[t]=false;
			ans-=dis;
		}
		printf("%lld\n",ans);
	}
}

P688. 「HEOI2014」大工程

Solution1

暴力枚举每两个节点，利用lca求解路径长度维护答案，复杂度 \(O(\sum k^2\log k)\)

OJ和洛谷上 \(80\) pts？这题有什么存在的意义？

Solution2

考虑需要求解的是树上的路径，自然地考虑到点分治，复杂度 \(O(qn\log n)\)

20 pts 直接拿下！

Solution 3

考虑 Solution2 相比于 Solution1 欠缺的是相关于 \(k\) 的时间复杂度，而又考虑到整个点分治需要求解的路径的端点仅与求解的 \(k\) 个点有关，因此可以建立 \(2k\) 个点的虚树，从而复杂度为 \(O(\sum k\log k)\)

终于拿下了！

code
#include <bits/stdc++.h>
using namespace std;

const int N=1e6;
int n,m;
struct Graph{
	int cnt,a,b;
	int head[N+5],to[(N<<1)+5],v[(N<<1)+5];
	void clear(){
		cnt=1;
		return ;
	}
	void add(int x,int y){
		v[cnt]=y;
		to[cnt]=head[x];
		head[x]=cnt++;
		return ;
	}
	void add_edge(){
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
}RG,IG;
struct LCA{
	int tot;
	int dep[N+5],siz[N+5],faz[N+5],son[N+5],top[N+5],dfn[N+5];
	void dfs1(int u){
		siz[u]=1;
		son[u]=0;
		for(int i=RG.head[u];i;i=RG.to[i]){
			int v=RG.v[i];
			if(v==faz[u])continue;
			faz[v]=u;
			dep[v]=dep[u]+1;
			dfs1(v);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
		return ;
	} 
	void dfs2(int u,int rt){
		top[u]=rt;
		dfn[u]=++tot;
		if(son[u])dfs2(son[u],rt);
		for(int i=RG.head[u];i;i=RG.to[i]){
			int v=RG.v[i];
			if(v==faz[u]||v==son[u])continue;
			dfs2(v,v);
		}
		return ;
	}
	void pre(){
		dfs1(1);
		dfs2(1,1);
		return ;
	}
	int lca(int x,int y){
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			x=faz[top[x]];
		}
		if(dep[x]<dep[y])swap(x,y);
		return y;
	}
	int dis(int x,int y){
		return dep[x]+dep[y]-2*dep[lca(x,y)];
	}
}Lca;
bool cmp(int x,int y){
	return Lca.dfn[x]<Lca.dfn[y];
}
struct PointTree{
	int k,tot,root,top;
	int dis[N+5],siz[N+5],maxp[N+5],lst[N+5],stk[N+5];
	long long sum,Min,Max,pre,nxt,pre_min,pre_max,nxt_min,nxt_max,cnt;
	bool vis[N+5],ask[N+5];
	long long min(long long a,long long b){
		return a<b?a:b;
	}
	long long max(long long a,long long b){
		return a>b?a:b;
	}
	void get_root(int u,int fa,int total){
		siz[u]=1;
		maxp[u]=0;
		for(int i=IG.head[u];i;i=IG.to[i]){
			int v=IG.v[i];
			if(v==fa||vis[v])continue;
			get_root(v,u,total);
			siz[u]+=siz[v];
			maxp[u]=max(maxp[u],siz[v]);
		}
		maxp[u]=max(maxp[u],total-siz[u]);
		if(maxp[u]<maxp[root])root=u;
		return ;
	}
	void get_siz(int u,int fa){
		siz[u]=1;
		for(int i=IG.head[u];i;i=IG.to[i]){
			int v=IG.v[i];
			if(v==fa||vis[v])continue;
			get_siz(v,u);
			siz[u]+=siz[v];
		}
		return ;
	}
	void get_dis(int u,int fa,int d){
		if(ask[u]){
			dis[++tot]=d;
			nxt+=d;
			++cnt;
			nxt_min=min(nxt_min,d);
			nxt_max=max(nxt_max,d);
		}
		for(int i=IG.head[u];i;i=IG.to[i]){
			int v=IG.v[i];
			if(v==fa||vis[v])continue;
			get_dis(v,u,d+Lca.dis(u,v));
		}
		return ;
	}
	void calc(int u){
		tot=pre=0;
		pre_max=-2e9;
		pre_min=2e9;
		if(ask[u]){
			dis[++tot]=0;
			pre_max=pre_min=0;
		}
		for(int i=IG.head[u];i;i=IG.to[i]){
			int v=IG.v[i];
			if(vis[v])continue;
			nxt=cnt=0;
			nxt_max=-2e9;
			nxt_min=2e9;
			get_dis(v,u,Lca.dis(u,v));
			sum+=nxt*(tot-cnt)+pre*cnt;
			Min=min(Min,pre_min+nxt_min);
			Max=max(Max,pre_max+nxt_max);
			pre+=nxt;
			pre_max=max(pre_max,nxt_max);
			pre_min=min(pre_min,nxt_min);
		}
		return ;
	}
	void dfs(int u){
		vis[u]=true;
		calc(u);
		ask[u]=false;
		for(int i=IG.head[u];i;i=IG.to[i]){
			int v=IG.v[i];
			if(vis[v])continue;
			root=0;
			get_root(v,0,siz[v]);
			get_siz(v,0);
			dfs(root);
		}
		vis[u]=false;
		IG.head[u]=0;
		return ;
	}
	void query(){
		sum=Max=0;
		Min=2e9;
		IG.clear();
		scanf("%d",&k);
		for(int i=1;i<=k;i++){
			scanf("%d",&lst[i]);
			ask[lst[i]]=true;
		}
		sort(lst+1,lst+1+k,cmp);
		stk[top=1]=lst[1];
		for(int i=2;i<=k;i++){
			int lc=Lca.lca(lst[i],stk[top]);
			while(1){
				if(Lca.dep[lc]>=Lca.dep[stk[top-1]]){
					if(lc!=stk[top]){
						IG.add(lc,stk[top]);
						IG.add(stk[top],lc);
						if(lc!=stk[top-1])stk[top]=lc;
						else --top;
					}
					break;
				}else{
					--top;
					IG.add(stk[top],stk[top+1]);
					IG.add(stk[top+1],stk[top]);
				}
			}
			stk[++top]=lst[i];
		}
		while(--top){
			IG.add(stk[top],stk[top+1]);
			IG.add(stk[top+1],stk[top]);
		}
		maxp[0]=n;
		root=0;
		get_root(stk[1],0,n);
		get_siz(stk[1],0);
		dfs(root);
		printf("%lld %lld %lld\n",sum,Min,Max);
		return ;
	}
}PT;

int main(){
	RG.clear();
	scanf("%d",&n);
	for(int i=1;i<n;i++)RG.add_edge();
	Lca.pre();
	scanf("%d",&m);
	for(int i=1;i<=m;i++)PT.query();
}

More solutions

无可否认的，这道题选用点分治无疑是杀鸡用牛刀，但是谁叫我不会推树形dp呢？因此，这道题可以利用各种各样的树上算法，例如树形dp，最后利用虚树优化即可。

P2015. 「ZJOI2019」语言

九条可怜狗都不做，先颓着。

P686. 「HNOI2014」世界树

I'm now thinking aout it.

标签：特殊,int,top,笔记,stk,学习,lca,节点,虚树
From： https://www.cnblogs.com/DycBlog/p/18059811

相关文章

  • 线性基学习笔记
    线性基学习笔记定义线性空间\(V\)内的一个极大线性无关组是\(V\)的一组hamel基或线性基，简称基。以上内容是OIWIKI中提及的定义。更具体一点来说，对于一个向量组\(v\)，如果满足对于任意的取值，使\(\sum_{i=1}^n\alpha_iv_i\ne0\)（\(\alpha\)是常数），即不回到原点，那......
  • 网络流学习笔记
    网络流学习笔记本来是不想写的，因为不想在里面博客插入图片，但是发现网络流似乎可以牵扯出许多不为人知的图论内容，因此特此写一篇博客铺路。前言网络流是一种说难也不难，说简单也不简单的结构。难就难在对于一道题来说，我们难以分辨需要用到什么算法，怎么建图，因此，我们只能多做多练，积......
  • 基环树学习笔记
    基环树学习笔记定义基环树指的是一张有\(n\)个节点和\(n\)条边的图，如果不保证连通的话，那么整张图是一张基环树森林。并且如果将环上的任意一条边去除，那么整棵基环树会成为一棵普通的树。分类基环树有以下几种特殊情况，也是题目中较多出现的。基环内向树指的是在一棵有向......
  • 笛卡尔树学习笔记
    笛卡尔树学习笔记定义笛卡尔树是一棵特殊的二叉树，它的每个节点都包含了两个值\((k,w)\)。其中，整棵树关于\(k\)为一棵二叉搜索树，而关于\(w\)为一个小根堆（或大根堆）。到这里可以发现，Treap是一种特殊的笛卡尔树，因为Treap相当于给定了\(k\)，而我们人为将其随机了一个\(w\)......
  • A星算法笔记
    A星算法笔记参考：https://blog.csdn.net/hitwhylz/article/details/23089415原理heuristic启发式F=G+HG:distancebetweenstartandcurrentnodeH:distancebetweengoalandcurrentnode//TOSEARCH&CHECKManhatan距离:基本数据结构1.全局数组：openlistclose......
  • java基础 韩顺平老师的 面向对象（基础） 自己记的部分笔记
    194，对象内存布局基本数据类型放在堆里面，字符串类型放在方法区。栈：一般存放基本数据类型（局部变量）堆：存放对象（Catcat，数组等）方法区：常量池（常量，比如字符串），类加载信息 196，属性注意细节1，属性可以是基本数据类型，也可以是引用类型（对象，数组）2，属性的定义语法同变量，示例：访问修饰符属......
  • Contrastive Learning 对比学习 | 何恺明大神的 SimSiam
    论文题目：ExploringSimpleSiameseRepresentationLearning，CVPR2021。pdf：https://arxiv.org/abs/2011.10566相关博客：知乎|无门槛级讲解对比学习中的自监督模型Simsiam（通俗易懂）知乎|对比学习（ContrastiveLearning）：研究进展精要（解释了为什么Simsiam会演变成这样）知......
  • 3/7学习进度
    大二学期第二周日报 第一天第二天第三天第四天第五天所花时间（包括上课） 190min≈3h≈4h  代码量（行） 75150行左右  0  博客量（篇） 1 1 1  了解到的知识点安装matlab，文件操作，安卓数据库操作复习 vue、axios......
  • Denoising Implicit Feedback for Recommendation论文阅读笔记
    Abstract​ 隐式反馈的普遍性使它们成为构建在线推荐系统的默认选择。虽然大量的隐式反馈缓解了数据的稀疏性问题，但缺点是它们在反映用户的实际满意度方面没有那么干净。例如，在电子商务中，很大一部分点击并不能转化为购买，许多购买最终会得到负面评论。因此，解释隐式反馈中不可避免......
  • mysql.h学习记录
    目录简介简介mysql.h是MySQLCAPI的主要头文件，它为C开发者提供了一套函数和定义，以与MySQL服务器交互。这些函数和定义使得开发者能够编写应用程序，实现与MySQL服务器的连接、执行查询、检索结果等操作。以下是一些常见的函数及其在mysql.h中的简要介绍：连接和关......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99