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

基环树学习笔记

时间：2024-03-07 21:34:24浏览次数：29  
标签：return 环上 int top 笔记 学习 基环树 void 节点

基环树学习笔记

定义

基环树指的是一张有 \(n\) 个节点和 \(n\) 条边的图，如果不保证连通的话，那么整张图是一张基环树森林。并且如果将环上的任意一条边去除，那么整棵基环树会成为一棵普通的树。

分类

基环树有以下几种特殊情况，也是题目中较多出现的。

基环内向树

指的是在一棵有向基环树中，所有节点有且仅有一条出边。如【P3437. [ZJOI2008]骑士】。

基环外向树

指的是在一棵有向基环树中，所有节点有且仅有一条入边。

常见处理方法

找环

对于任何一棵基环树，与普通的树最大的不同就是上面存在一个环，我们如果想将其看作普通的树或环来处理，那么就必须先找到上面的环。下面是对于不同的基环树常见的找环方式。

无向图

dfs

这种写法更适用与需要确切找到从某个节点出发到达的第一个环上的节点。

void dfs(int u,int fa){
	if(ins[u]){
		int j;
		mark[u]=true;
		for(j=top;stk[j]!=u;j--)mark[stk[j]]=true;
		return ;
	}
	if(vis[u])return ;
	stk[++top]=u;
	vis[u]=ins[u]=true;
	for(int i=G.head[u];i;i=G.to[i]){
		int v=G.v[i];
		if(v==fa)continue;
		dfs(v);
	}
	top--;
	ins[u]=false;
	return ;
}
拓扑排序
void topo(){
	for(int i=1;i<=n;i++){
		if(!in[i])q.push(i);
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=to[i]){
			int y=v[i],z=w[i];
			if(--in[y]==0)q.push(y);
		}
	}
}

有向图

dfs

有向图找环的代码与无向图的 dfs 类似。

void dfs(int u){
	if(ins[u]){
		int j;
		mark[u]=true;
		for(j=top;stk[j]!=u;j--)mark[stk[j]]=true;
		return ;
	}
	if(vis[u])return ;
	stk[++top]=u;
	vis[u]=ins[u]=true;
	for(int i=G.head[u];i;i=G.to[i]){
		int v=G.v[i];
		dfs(v);
	}
	top--;
	ins[u]=false;
	return ;
}

处理

处理方法常见的通常有树形 dp 和环形 dp 两种。

树形 dp

因为基环树并非普通的树，所以需要先去除环上的一条边，使整张图变成一棵树才能正常开始 dp，并且又因为去除掉了一条边，所以会有两个节点的限制关系被消除，因此通常需要进行两次 dp。

环形 dp

抛去除了环上所有节点以外的所有节点，整张图会变成一个环，接着可以跑一遍环形 dp。因为不能凭空去除一些节点，就需要另行将去除掉的节点的信息添加到相连接的环上的节点上。

例题

P3437. [ZJOI2008]骑士

Solution1

这道题每个人都有一个讨厌的人，如果从每个人出发，向自己讨厌的人建一条有向边，那么这是一棵基环内向树。再考虑到每个人不能和讨厌的人一起去，那么思路和【P280. 没有上司的舞会】相同，可以利用树形 dp 求解。但是又考虑到去掉的一条边的两个节点不可以都去，那么意味着一定有一个人不去，那么在跑完两次树形 dp 后，只选择根节点不去的最小方案即可。

code1

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=1e6+5,Inf=-2147483647;
int n,cnt=1,mark;
int head[N],w[N],d[N];
ll ans;
ll f[N][2];
bool vis[N];
struct edge{
	int v,to;
}e[N];

void addEdge(int u,int v){
	e[cnt].v=v,e[cnt].to=head[u];
	head[u]=cnt++;
}

void check(int x){
	vis[x]=true;
	if(vis[d[x]])mark=x;
	else check(d[x]);
	return ;
}

void dfs(int u){
	vis[u]=true;
	f[u][1]=w[u],f[u][0]=0;
	for(int i=head[u];i;i=e[i].to){
		int v=e[i].v;
		if(v==mark)f[v][1]=Inf;
		else{
			dfs(v);
			f[u][0]+=max(f[v][0],f[v][1]);
			f[u][1]+=f[v][0];
		}
	}
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>d[i];
		addEdge(d[i],i);
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		check(i);
		dfs(mark);
		ll Max=f[mark][0];
		mark=d[mark];
		dfs(mark);
		ans+=max(Max,f[mark][0]);
	}
	cout<<ans;
}

P1203. 「NOIP2018」旅行

Solution1

观察到数据范围中的 \(m=n\) 或 \(m=n-1\)，就应该分类讨论。

m=n-1

此时，整张图为一棵树。因为无法回到已经去过的节点，那么就只能走完一棵子树再走另一棵子树，为了实现选择子树最小值，我选择了邻接矩阵存图。

m=n

此时，整张图为一棵基环树。考虑在走到环之后怎么操作，优先走编号更小的点，也就是说，第一个到达的在环上的节点的两个环上相邻的节点中，编号最小的会优先被走到。接着考虑什么时候舍弃一边转而走到另一边，很显然在找编号最小的点时，可能会错过一些点的子树而直接走到环上的另一个点，那么在上一个点就会存留一些剩余的点没有走过，而当回溯的时候是必要走过这些点的。显然，如果下一个环上的节点的编号，比上一个有剩余子树的节点的剩余最小值要大，那么我们不如直接回溯，这样的字典序一定最小。或者当没有剩余子树并且环上节点比之前未被选择的一侧的节点的编号要大，那么我们不如回溯去走那个未被选择的点，这样的字典序一定最小。当我们选择完一侧的节点，另一侧的节点就可以当作普通的树求解了。

code1

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

const int N=5e3;
int n,m,x,y,top,fir,sec,unv;
int stk[N+5];
bool g[N+5][N+5],mark[N+5],ins[N+5],vis[N+5],vis2[N+5];

void dfs1(int u,int fa){
	printf("%d ",u);
	for(int i=1;i<=n;i++){
		if(!g[u][i]||i==fa)continue;
		dfs1(i,u);
	}
	return ;
}

void dfs2(int u,int fa){
	stk[++top]=u;
	ins[u]=vis[u]=true;
	for(int i=1;i<=n;i++){
		if(!g[u][i]||i==fa)continue;
		if(ins[i]){
			int j;
			for(j=top;stk[j]!=i;j--){
				mark[stk[j]]=true;
				ins[stk[j]]=false;
			}
			mark[i]=true;
			fir=min(u,stk[j+1]);
			sec=max(u,stk[j+1]);
			return ;
		}
		if(!vis[i])dfs2(i,u);
	}
	--top;
	ins[u]=false;
	return ;
}

void dfs5(int u,int fa){
	printf("%d ",u);
	vis2[u]=true;
	for(int i=1;i<=n;i++){
		if(!g[u][i]||i==fa||vis2[i])continue;
		dfs5(i,u);
	}
	return ;
}

void dfs4(int u,int fa){
	printf("%d ",u);
	vis2[u]=true;
	for(int i=1;i<=n;i++){
		if(!g[u][i]||i==fa||vis2[i])continue;
		if(mark[i]){
			for(int j=i+1;j<=n;j++){
				if(!g[u][j]||j==fa)continue;
				unv=j;
				break;
			}
			if((sec<i&&unv==n+1)||unv<i){
				for(int j=i+1;j<=n;j++){
					if(j==fa||!g[u][j])continue;
					dfs5(j,u);
				}
				return ;
			}
			dfs4(i,u);
		}else dfs5(i,u);
	}
	return ;
}

void dfs3(int u,int fa){
	printf("%d ",u);
	vis2[u]=true;
	if(mark[u]){
		for(int i=1;i<=n;i++){
			if(!g[u][i]||i==fa||vis2[i])continue;
			if(i==fir)dfs4(fir,u);
			else if(i==sec)dfs5(sec,u);
			else dfs3(i,u);
		}
		return ;
	}
	for(int i=1;i<=n;i++){
		if(!g[u][i]||i==fa)continue;
		dfs3(i,u);
	}
	return ;
}

int main(){
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		g[x][y]=g[y][x]=true;
	}
	if(m==n-1)dfs1(1,0);
	else{
		dfs2(1,0);
		unv=n+1;
		dfs3(1,0);
	}
	return 0;
}

P3438. [Ioi2008] Island 岛屿

Solution1

问题即求每个基环树的最长链的长度。考虑将环上的每个节点的子树合并到环上，然后考虑环上的最长链。令 \(g_i\) 表示以 \(i\) 为根的子树中的最长链，\(f_i\) 表示以 \(i\) 为根节点的子树中以 \(i\) 为起点的最长链，\(s\) 为环长，\(dis_{i,j}\) 表示环上 \(i,j\) 两点的距离，对于环上的两个节点 \(u,v\)，与其相关的链可能是 \(g_u,g_v,f_u+f_v+dis_{u,v},f_u+f_v+s-dis_{u,v}\)，在其中取最大值即可。利用单调队列的思想，令 \(dis_i\) 表示环上到 \(i\) 时的边权和，后两者相当于 \((f_u-dis_u)+(f_v+dis_v),(f_u+dis_u)+(f_v-dis_v)+s\)，利用单调队列维护 \(f_u-dis_u,f_u+dis_u\) 的最大值。

code1

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

const int N=1e6;
int n;
int v[N+5],w[N+5],in[N+5];
long long ans;
long long f[N+5],g[N+5];
queue<int>q;

long long GetAns(int p){
	int tmp=p;
	p=v[p];
	long long ans1=g[tmp],ans2=-1e18,s=w[tmp],m1=f[tmp],m2=f[tmp];
	while(p!=tmp){
		in[p]=0;
		ans1=max(ans1,max(g[p],f[p]+s+m1));
		ans2=max(ans2,f[p]-s+m2);
		m1=max(m1,f[p]-s);
		m2=max(m2,f[p]+s);
		s+=w[p];
		p=v[p];
	}
	return max(ans1,ans2+s);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&v[i],&w[i]);
		in[v[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(!in[i])q.push(i);
	}
	while(!q.empty()){
		int p=q.front();
		q.pop();
		long long sum=f[p]+w[p];
		g[v[p]]=max(g[v[p]],max(f[v[p]]+sum,g[p]));
		f[v[p]]=max(f[v[p]],sum);
		if(--in[v[p]]==0)q.push(v[p]);
	}
	for(int i=1;i<=n;i++){
		if(in[i])ans+=GetAns(i);
	}
	printf("%lld",ans);
	return 0;
}

P3439. [POI2012] Rendezvous

Solution1

首先，题目中的图是基环内向树森林。考虑到对于一棵联通的基环树，环上的每一个节点都有自己的子树。如果 \(a\) 和 \(b\) 在同一个环上节点的子树内，那么它们的最优相遇位置一定是在它们的最近公共祖先处。而如果它们不在一个环上节点的子树内，那么最优的相遇位置要么在 \(a\) 所属的环上节点，要么在 \(b\) 所属的环上节点，我们求解两个环上节点之间的距离和环的大小并分类讨论，然后根据题面要求判断更优解即可。

code1

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

const int N=5e5;
int n,m;
struct DSU{
	int faz[N+5];
	void build(){
		for(int i=1;i<=n;i++)faz[i]=i;
		return ;
	}
	int find(int x){
		if(faz[x]==x)return x;
		return faz[x]=find(faz[x]);
	}
	void insert(int x,int y){
		int X=find(x),Y=find(y);
		if(X==Y)return ;
		faz[X]=Y;
		return ;
	}
}Dsu;
struct Graph{
	int cnt1,cnt2;
	int head1[N+5],to1[N+5],v1[N+5],head2[N+5],to2[N+5],v2[N+5];
	void add1(int x,int y){
		to1[cnt1]=head1[x];
		v1[cnt1]=y;
		head1[x]=cnt1++;
		return ;
	}
	void add2(int x,int y){
		to2[cnt2]=head2[x];
		v2[cnt2]=y;
		head2[x]=cnt2++;
		return ;
	}
	void build(){
		int y;
		cnt1=cnt2=1;
		for(int x=1;x<=n;x++){
			scanf("%d",&y);
			add1(x,y);
			add2(y,x);
			Dsu.insert(x,y);
		}
		return ;
	}
}G;
struct Circle_Tree{
	int top;
	int stk[N+5];
	bool vis[N+5],ins[N+5],mark[N+5];
	void dfs(int u){
		if(ins[u]){
			int j;
			mark[u]=true;
			for(j=top;stk[j]!=u;j--){
				mark[stk[j]]=true;
				ins[stk[j]]=true;
			}
			return ;
		}
		if(vis[u])return ;
		stk[++top]=u;
		vis[u]=ins[u]=true;
		for(int i=G.head1[u];i;i=G.to1[i]){
			int v=G.v1[i];
			dfs(v);
		}
		top--;
		ins[u]=false;
		return ;
	}
	void build(){
		for(int i=1;i<=n;i++){
			if(!vis[i])dfs(i);
		}
		return ;
	}
}Ct;
struct LCA{
	int Siz;
	int R[N+5],faz[N+5],siz[N+5],son[N+5],top[N+5],dep[N+5],dis[N+5],len[N+5];
	bool vis[N+5];
	void dfs1(int u,int rt){
		R[u]=rt;
		siz[u]=1;
		for(int i=G.head2[u];i;i=G.to2[i]){
			int v=G.v2[i];
			if(Ct.mark[v])continue;
			faz[v]=u;
			dep[v]=dep[u]+1;
			dfs1(v,rt);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
		return ;
	}
	void dfs2(int u,int rt){
		top[u]=rt;
		if(son[u])dfs2(son[u],rt);
		for(int i=G.head2[u];i;i=G.to2[i]){
			int v=G.v2[i];
			if(Ct.mark[v]||v==son[u])continue;
			dfs2(v,v);
		}
		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;
	}
	void dfs3(int u){
		Siz++;
		vis[u]=true;
		for(int i=G.head1[u];i;i=G.to1[i]){
			int v=G.v1[i];
			if(vis[v])continue;
			dis[v]=dis[u]+1;
			dfs3(v);
		}
		len[u]=Siz;
		return ;
	}
	void build(){
		for(int i=1;i<=n;i++){
			if(Ct.mark[i]){
				dfs1(i,i);
				dfs2(i,i);
			}
		}
		for(int i=1;i<=n;i++){
			if(Ct.mark[i]&&!vis[i]){
				Siz=0;
				dfs3(i);
			}
		}
		return ;
	}
}Lca;
struct Query{
	void query(int a,int b){
		int A=Dsu.find(a),B=Dsu.find(b);
		if(A!=B)printf("-1 -1\n");
		else if(Lca.R[a]==Lca.R[b]){
			int lc=Lca.lca(a,b);
			printf("%d %d\n",Lca.dep[a]-Lca.dep[lc],Lca.dep[b]-Lca.dep[lc]);
		}else{
			int x=Lca.R[a],y=Lca.R[b],dis=Lca.dis[x]-Lca.dis[y],disA=Lca.dep[a],disB=Lca.dep[b],A1,A2,B1,B2;
			if(dis<0){
				A1=disA-dis;
				B1=disB;
				A2=disA;
				B2=disB+Lca.len[y]+dis;
			}else{
				A1=disA+Lca.len[x]-dis;
				B1=disB;
				A2=disA;
				B2=disB+dis;
			}
			if(max(A1,B1)<max(A2,B2))printf("%d %d\n",A1,B1);
			else if(max(A1,B1)>max(A2,B2))printf("%d %d\n",A2,B2);
			else{
				if(min(A1,B1)<min(A2,B2))printf("%d %d\n",A1,B1);
				else if(min(A1,B1)>min(A2,B2))printf("%d %d\n",A2,B2);
				else{
					if(A1>=B1)printf("%d %d\n",A1,B1);
					else printf("%d %d\n",A2,B2);
				}
			}
		}
		return ;
	}
	void build(){
		int a,b;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&a,&b);
			query(a,b);
		}
		return ;
	}
}Q;

int main(){
	scanf("%d%d",&n,&m);
	Dsu.build();
	G.build();
	Ct.build();
	Lca.build();
	Q.build();
	return 0;
}

P3441. 创世纪

Solution1

考虑将环上的一条边去掉，进行树形 dp，但问题中的基环内向树无法树形 dp，因此需要建反图，使整张图变为基环外向树，接着去除掉唯一一条到根节点的入边使其成为一棵树。接着考虑限制如何补回来，考虑到去除的一条边会使根节点的一个限制消失。当根节点不选时，原本被限制的点因为已经有根节点未被选择，所以剩下的限制节点可以随意选择。而当根节点选择时，则原本被限制的点的限制条件和其他点一样。可以利用两个 dfs 处理。

code1

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

const int N=1e6;
int n,ans;
struct Graph{
	int cnt;
	int head[N+5],to[N+5],v[N+5];
	void add(int x,int y){
		v[cnt]=y;
		to[cnt]=head[x];
		head[x]=cnt++;
		return ;
	}
	void build(){
		int x;
		cnt=1;
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			add(x,i);
		}
		return ;
	}
}G;
struct Circle_Tree{
	int top,rt,mark;
	int stk[N+5],f[N+5],g[N+5];
	bool flag;
	bool ins[N+5],vis[N+5];
	void dfs1(int u){
		if(ins[u]){
			flag=true;
			rt=u;
			mark=stk[top];
			return ;
		}
		if(vis[u])return ;
		vis[u]=ins[u]=true;
		stk[++top]=u;
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i];
			dfs1(v);
		}
		--top;
		ins[u]=false;
		return ;
	}
	void dfs2(int u){
		f[u]=1;
		g[u]=0;
		bool flag=1; 
		int sum=0,Min=0,cnt=0;
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i];
			if(u==mark&&v==rt)continue;
			cnt++;
			dfs2(v);
			if(f[v]>g[v]){
				sum+=f[v];
				Min=min(Min,g[v]-f[v]);
			}else{
				sum+=g[v];
				flag=0;
			}
		}
		g[u]+=sum;
		if(flag)f[u]+=sum+Min;
		else f[u]+=sum;
		if(!cnt)f[u]=-N;
		return ;
	}
	void dfs3(int u){
		f[u]=1;
		g[u]=0;
		bool flag=1; 
		int sum=0,Min=0,cnt=0;
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i];
			if(u==mark&&v==rt)continue;
			cnt++;
			dfs3(v);
			if(f[v]>g[v]){
				sum+=f[v];
				Min=min(Min,g[v]-f[v]);
			}else{
				sum+=g[v];
				flag=0;
			}
		}
		g[u]+=sum;
		if(u==mark||!flag)f[u]+=sum;
		else f[u]+=sum+Min;
		if(!cnt&&u!=mark)f[u]=-N;
		return ;
	}
	void build(){
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				flag=false;
				dfs1(i);
				if(flag){
					int A=0; 
					dfs2(rt);
					A=max(A,f[rt]);
					dfs3(rt);
					A=max(A,g[rt]);
					ans+=A;
				}
			}
		}
		return ;
	}
}Ct;

int main(){
	scanf("%d",&n);
	G.build();
	Ct.build();
	printf("%d",ans);
}

P3440. Freda的传呼机

Solution1

看到题面，如同【P1203. 「NOIP2018」旅行】一样的，考虑分类讨论。

m=n-1

此时，整张图为一颗树，那么利用 lca 求解即可。

贴心的帮你们测试了，这种情况占 \(30\) pts。

m=n

此时整张图为一棵基环树，和【P3439. [POI2012] Rendezvous】类似的，当两个节点在同一个环上节点的子树内部时利用 lca 求解，否则利用环上两点的简单路径只有两条并且经过环上所有边求解。

贴心的帮你们测试了，这种情况占 \(50\) pts。

每条光缆只在一个环中

这是仙人掌图，还没有学到（只是后面的内容），以后再来探索吧。波波也说足够了。

code1(\(80\) pts)

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

const int N=1e4,M=1.2e4;
int n,m,q;
struct Graph{
	int cnt;
	int head[N+5],to[(M<<1)+5],v[(M<<1)+5],w[(M<<1)+5];
	void add(int x,int y,int z){
		to[cnt]=head[x];
		v[cnt]=y;
		w[cnt]=z;
		head[x]=cnt++;
		return ;
	}
	void build(){
		int x,y,t;
		cnt=1;
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&x,&y,&t);
			add(x,y,t);
			add(y,x,t);
		}
		return ;
	}
}G;
struct Tree{
	int faz[N+5],siz[N+5],son[N+5],top[N+5],dep[N+5];
	long long dis[N+5];
	void dfs1(int u){
		siz[u]=1;
		son[u]=0;
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i],w=G.w[i];
			if(v==faz[u])continue;
			faz[v]=u;
			dep[v]=dep[u]+1;
			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){
		top[u]=rt;
		if(son[u])dfs2(son[u],rt);
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i];
			if(v==faz[u]||v==son[u])continue;
			dfs2(v,v);
		}
		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;
	}
	long long get_dis(int x,int y){
		return dis[x]+dis[y]-2*dis[lca(x,y)];
	}
	void build(){
		int x,y;
		dfs1(1);
		dfs2(1,1);
		while(q--){
			scanf("%d%d",&x,&y);
			printf("%lld\n",get_dis(x,y));
		}
		return ;
	}
}T;
struct Circle_Tree{
	int Top;
	int stk[N+5],R[N+5],faz[N+5],dep[N+5],siz[N+5],top[N+5],son[N+5];
	long long sum;
	long long dis[N+5],len[N+5];
	bool mark[N+5],ins[N+5],vis[N+5];
	void dfs4(int rt,int u,int fa){
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i],w=G.w[i];
			if(v==fa||!mark[v])continue;
			if(v==rt){
				sum+=w;
				continue;
			}
			len[v]=len[u]+w;
			sum+=w;
			dfs4(rt,v,u);
		}
		return ;
	}
	void dfs1(int u,int fa){
		if(ins[u]){
			mark[u]=true;
			for(int j=Top;stk[j]!=u;j--)mark[stk[j]]=true;
			dfs4(u,u,fa);
			return ;
		}
		if(vis[u])return ;
		stk[++Top]=u;
		ins[u]=vis[u]=true;
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i];
			if(v==fa)continue;
			dfs1(v,u);
		}
		--Top;
		ins[u]=false;
		return ;
	}
	void dfs2(int u,int rt){
		siz[u]=1;
		son[u]=0;
		R[u]=rt;
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i],w=G.w[i];
			if(v==faz[u]||mark[v])continue;
			dep[v]=dep[u]+1;
			faz[v]=u;
			dis[v]=dis[u]+w;
			dfs2(v,rt);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
		return ;
	}
	void dfs3(int u,int rt){
		top[u]=rt;
		if(son[u])dfs3(son[u],rt);
		for(int i=G.head[u];i;i=G.to[i]){
			int v=G.v[i];
			if(v==faz[u]||v==son[u]||mark[v])continue;
			dfs3(v,v);
		}
		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;
	}
	long long get_dis(int x,int y){
		if(R[x]==R[y])return dis[x]+dis[y]-2*dis[lca(x,y)];
		long long Len=abs(len[R[x]]-len[R[y]]);
		return dis[x]+dis[y]+min(Len,sum-Len);
	}
	void build(){
		int x,y;
		dfs1(1,0);
		for(int i=1;i<=n;i++){
			if(mark[i]){
				dfs2(i,i);
				dfs3(i,i);
			}
		}
		while(q--){
			scanf("%d%d",&x,&y);
			printf("%lld\n",get_dis(x,y));
		}
		return ;
	}
}Ct;

int main(){
	scanf("%d%d%d",&n,&m,&q);
	G.build();
	if(m==n-1)T.build();
	else if(m==n)Ct.build();
	return 0;
}

标签：return,环上,int,top,笔记,学习,基环树,void,节点
From： https://www.cnblogs.com/DycBlog/p/18059808

相关文章

  • 笛卡尔树学习笔记
    笛卡尔树学习笔记定义笛卡尔树是一棵特殊的二叉树，它的每个节点都包含了两个值\((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中的简要介绍：连接和关......
  • 旧时 科大部分物理笔记
    （怎么不见了这么多，后期纸制笔记未录入）有心力的角速度上的惯性离心势能势能（\(l\)为角动量）：\(E_p=-\dfrac{1}{2}mw^2r^2=\dfrac{l^2}{2mr^2}\)(由\(l=mrv_\theta\)和动能分量\(\dfrac{1}{2}mv_\theta^2\)得)有效势能（总势能）对位置求导为0的是平衡点，其中二阶导大于\(0\)的是......
  • 【学习笔记】 - 基础数据结构 ：Link-Cut Tree(进阶篇)
    前言LCT没题写可以去写树剖和一些线段树合并的题练手LCT的概念原本的树剖是对树进行剖分，剖分为重边和轻边LCT则是对于树分为虚边和实边，特殊的，LCT可以没有虚边(例：银河英雄传说v2)单独被包含在一个实链里的点称作孤立点在树剖中，我们使用线段树/树状数组来维护重链在Link-Cut......
  • Vue学习笔记39--创建Vue脚手架
    创建Vue脚手架1.Vue脚手架是Vue官方提供的标准开发工具(开发平台)2.脚手架最新版本4.x3.文档：https://cli.vuejs.org/zh/操作步骤：第一步：(仅第一次执行)：全局安装@vue/cli(commandlineinterface)注：安装钱建议先设置镜像==》npmconfigsetregisterhttps://registry.npm.taoba......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99