封装求助
  • 板块灌水区
  • 楼主蒟酱厂妹
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/3/25 09:54
  • 上次更新2023/10/23 20:37:39
查看原帖
封装求助
310818
蒟酱厂妹楼主2023/3/25 09:54
struct sp{
	std::vector<int>fa,dep,gs,top,sz;
	sp():fa(n+1),dep(n+1),gs(n+1),top(n+1),sz(n+1){}
	void dfs1(int u){
		for(auto[v,w]:g1[u]){
			if(v==fa[u])continue;
			fa[v]=u,dep[v]=dep[u]+1,sz[v]=1;
			dfs1(v);sz[u]+=sz[v];
			if(sz[v]>sz[gs[u]])gs[u]=v;
		}
	}
	void dfs2(int u,int t){
		top[u]=t;if(!gs[u])return;else dfs2(gs[u],t);
		for(auto[v,w]:g1[u])if(v!=fa[u]&&v!=gs[u])dfs2(v,v);
	}
	int LCA(int x,int y){
		for(;top[x]!=top[y];x=fa[top[x]])if(dep[top[x]]<dep[top[y]])std::swap(x,y);
		return dep[x]<dep[y]?x:y;
	};
};

这是一段树剖 LCA 代码,发现构造函数很长

std::vector<int>fa,dep,gs,top,sz;
sp():fa(n+1),dep(n+1),gs(n+1),top(n+1),sz(n+1){}

有没有简短点的办法,比如

std::vector<int>fa(n+1),dep(n+1),gs(n+1),top(n+1),sz(n+1);

不过这样会 CE

2023/3/25 09:54
加载中...