建虚树时这两种方法有什么区别？
查看原帖
建虚树时这两种方法有什么区别？
643820
WangLianda楼主2023/2/14 17:56

这里建树的方法是：

把点按dfn排序，相邻点的lca丢进去，去重之后再按dfn排序，每个点在虚树上的父亲就是自己和前驱的lca。

这样去重就有了两种方法：

一种是先sort排序，再unique去重，再按照dfn排序

另一种是先按dfn排序，再unique去重

但是第二种方法就是会T，这有什么区别吗？同一大小的数，如果用dfn排序的话，也应该会被排到相邻的位置吧。

第一种方法的代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
int n;
int dfn[250005],cnt;
vector<vector<pair<int,int>>> a;
vector<pair<int,int>> b[250005];
bool cmp(int a,int b) {
	return dfn[a]<=dfn[b];
}
int f[20][250005],g[20][250005];
//g[k][i]表示从i节点向上走2^k条边，经过的最小边权 
int *fa=f[0],size[250005],son[250005],top[250005],deep[250005];
int dfs1(int u) {
	size[u]=1;
	deep[u]=deep[fa[u]]+1;
	for(auto&i:a[u]) {
		int v=i.first,p=i.second;
		if(v==fa[u]) continue;
		fa[v]=u; 
		g[0][v]=p;
		size[u]+=dfs1(v);
		if(size[son[u]]<size[v]) son[u]=v;
	}
	return size[u];
}
void dfs2(int u) {
	if(son[fa[u]]==u) top[u]=top[fa[u]];
	else top[u]=u;
	dfn[u]=++cnt;
	if(son[u]) dfs2(son[u]);
	for(auto&i:a[u]) {
		int v=i.first;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v);
	}
}
int LCA(int x,int y) {
	if(deep[x]<deep[y]) swap(x,y);
	for(int k=19;k>=0;k--)
		if(deep[f[k][x]]>=deep[y])
			x=f[k][x];
	if(x==y) return x;
	for(int k=19;k>=0;k--)
		if(f[k][x]^f[k][y])
			x=f[k][x],
			y=f[k][y];
	return fa[x];
}
int find(int x,int y) {
	//deep[x]>deep[y]
	int ans=INT_MAX;
	for(int k=19;k>=0;k--)
		if(deep[f[k][x]]>=deep[y])
			ans=min(ans,g[k][x]),
			x=f[k][x];
	return ans;
}
long long h[250005];
bool w[250005];
long long dfs3(int u) {
	h[u]=0;
	if(w[u]) h[u]=1e14,w[u]=0;
	for(auto&i:b[u]) {
		int v=i.first,p=i.second;
		h[u]+=min(dfs3(v),(long long)p);
	}
	return h[u];
}
int lca[250005];
int x[500005],num;
int main() {
	for(auto&i:g)
		for(auto&j:i)
			j=INT_MAX;
	cin>>n;
	a.resize(n+1);
	for(int i=1;i<n;i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
	dfs1(1);
	dfs2(1);
	for(int k=1;k<20;k++)
		for(int i=1;i<=n;i++)
			f[k][i]=f[k-1][f[k-1][i]],
			g[k][i]=min(g[k-1][i],g[k-1][f[k-1][i]]);
	int m;
	cin>>m;
	while(m--) {
		num=0;
		x[num++]=1;
		int K;
		scanf("%d",&K);
		for(int i=1;i<=K;i++) {
			int y;
			scanf("%d",&y);
			w[y]=1;
			x[num++]=y;
		}
		sort(x,x+num,cmp);
//		cout<<"***";
//		for(auto&i:x) cout<<i<<' ';
//		cout<<"***"<<endl;
		for(int i=1;i<=K;i++) {
			int L=LCA(x[i],x[i-1]);
			if(L^x[i]&&L^x[i-1])
				x[num++]=L;
		}
		sort(x,x+num);//按普通顺序排序，去重 
		num=unique(x,x+num)-x;
		sort(x,x+num,cmp);//按dfs序排序 
//		cout<<"***";
//		for(auto&i:x) cout<<i<<' ';
//		cout<<"***"<<endl;
		for(int i=1;i<num;i++) {
			lca[i]=LCA(x[i],x[i-1]);
			int p=find(x[i],lca[i]);
			b[lca[i]].push_back({x[i],p});
		}
		printf("%lld\n",dfs3(1));
		for(int i=1;i<num;i++) 
			if(b[lca[i]].size())
				b[lca[i]].resize(0);
	}
	return 0;
}

第二种方法的代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
int n;
int dfn[250005],cnt;
vector<vector<pair<int,int>>> a;
vector<pair<int,int>> b[250005];
bool cmp(int a,int b) {
	return dfn[a]<=dfn[b];
}
int f[20][250005],g[20][250005];
//g[k][i]表示从i节点向上走2^k条边，经过的最小边权 
int *fa=f[0],size[250005],son[250005],top[250005],deep[250005];
int dfs1(int u) {
	size[u]=1;
	deep[u]=deep[fa[u]]+1;
	for(auto&i:a[u]) {
		int v=i.first,p=i.second;
		if(v==fa[u]) continue;
		fa[v]=u; 
		g[0][v]=p;
		size[u]+=dfs1(v);
		if(size[son[u]]<size[v]) son[u]=v;
	}
	return size[u];
}
void dfs2(int u) {
	if(son[fa[u]]==u) top[u]=top[fa[u]];
	else top[u]=u;
	dfn[u]=++cnt;
	if(son[u]) dfs2(son[u]);
	for(auto&i:a[u]) {
		int v=i.first;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v);
	}
}
int LCA(int x,int y) {
	if(deep[x]<deep[y]) swap(x,y);
	for(int k=19;k>=0;k--)
		if(deep[f[k][x]]>=deep[y])
			x=f[k][x];
	if(x==y) return x;
	for(int k=19;k>=0;k--)
		if(f[k][x]^f[k][y])
			x=f[k][x],
			y=f[k][y];
	return fa[x];
}
int find(int x,int y) {
	//deep[x]>deep[y]
	int ans=INT_MAX;
	for(int k=19;k>=0;k--)
		if(deep[f[k][x]]>=deep[y])
			ans=min(ans,g[k][x]),
			x=f[k][x];
	return ans;
}
long long h[250005];
bool w[250005];
long long dfs3(int u) {
	h[u]=0;
	if(w[u]) h[u]=1e14,w[u]=0;
	for(auto&i:b[u]) {
		int v=i.first,p=i.second;
		h[u]+=min(dfs3(v),(long long)p);
	}
	return h[u];
}
int lca[250005];
int x[500005],num;
int main() {
	for(auto&i:g)
		for(auto&j:i)
			j=INT_MAX;
	cin>>n;
	a.resize(n+1);
	for(int i=1;i<n;i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
	dfs1(1);
	dfs2(1);
	for(int k=1;k<20;k++)
		for(int i=1;i<=n;i++)
			f[k][i]=f[k-1][f[k-1][i]],
			g[k][i]=min(g[k-1][i],g[k-1][f[k-1][i]]);
	int m;
	cin>>m;
	while(m--) {
		num=0;
		x[num++]=1;
		int K;
		scanf("%d",&K);
		for(int i=1;i<=K;i++) {
			int y;
			scanf("%d",&y);
			w[y]=1;
			x[num++]=y;
		}
		sort(x,x+num,cmp);
//		cout<<"***";
//		for(auto&i:x) cout<<i<<' ';
//		cout<<"***"<<endl;
		for(int i=1;i<=K;i++) {
			int L=LCA(x[i],x[i-1]);
			if(L^x[i]&&L^x[i-1])
				x[num++]=L;
		}
		sort(x,x+num,cmp);
		num=unique(x,x+num)-x;
//		cout<<"***";
//		for(auto&i:x) cout<<i<<' ';
//		cout<<"***"<<endl;
		for(int i=1;i<num;i++) {
			lca[i]=LCA(x[i],x[i-1]);
			int p=find(x[i],lca[i]);
			b[lca[i]].push_back({x[i],p});
		}
		printf("%lld\n",dfs3(1));
		for(int i=1;i<num;i++) 
			if(b[lca[i]].size())
				b[lca[i]].resize(0);
	}
	return 0;
}
2023/2/14 17:56