自动搬运

查看原文

来自洛谷，原作者为

	阿丑 ArrTue

搬运于2025-08-24 22:39:39，当前版本为作者最后更新于2022-08-05 22:11:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

前置知识：

基环树。

题意：

• 给出 $n$ 个点和 $n$ 条有向边，每条边经过一次后会变为无向边。
• 从 $1$ 号点出发，经过若干条边依次到达 $2$ 号点、三号点……一直到 $x$ 号点，将经过的总边数最小值记为 $f_x$。
• 对于每一个 $x\in[1,n]$，求 $f_x$。
• $n\le5\times10^5$。保证 $1$ 号点可以到达任何点。

分析：

Subtask 0：

考虑 dfs 来枚举每一种方案。开一个数组来表示每一条边是有向边还是无向边，在移动前先判断一条边是否能走。

实际能过 $n\le6$。

Subtask 1：

考虑优化暴力的 dfs。将边的状态进行状态压缩：用一个 $n$ 位二进制数表示边的状态，第 $i$ 位为 $0$ 表示第 $i$ 条边为有向边，为 $1$ 表示第 $i$ 条边为无向边。设 $dp_{step,x,s}$ 表示已经完成了 $f_{step}$，当前位于 $x$ 号点，边的状态为 $s$ 的最小步数。枚举下一步的移动来进行转移。在移动前判断是否能走，移动后更新 $s$ 和 $step$。由于每次移动距离增加 $1$，可以写成 bfs。

时间复杂度 $\mathcal O(n^22^n)$。

Subtask 2：

由于 $1$ 号点能到达任何点，所以图弱联通。若边是无向边，则图是一棵基环树。

对较大的样例使用瞪眼法可得，有很多边的状态是不需要存储的，可以直接把它们当做双向边考虑。观察哪些边不需要存储。

对于外向树的情况，即只有 $n-1$ 条有向边、$1$ 号点作为树根时，若到达了 $i$ 号点，则意味着从到根节点到 $i$ 的路径上所有边都已走过，所以可以从 $i$ 到达任意祖先，因此从 $i$ 到 $i+1$ 一定可以沿着树上的最短路走，与所有边均为无向边的情况是一样的，所以不需要存储任何边的状态。

考虑拓展到基环树上。对于环上挂着的树，其实与单独的外向树并无不同，不需要存储边的状态。所以只需考虑环上的边的状态。

因为 $1$ 号点可以到达所有点，所以一般来说，一个环由两条方向相反的链组成，如样例一：

称两链的终点相交的位置为“关键点”。在样例一中，关键点即为 $6$ 号点。

与外向树一样，我们考虑将所有的边替换为无向边的情况。发现有向与无向的区别在于能否“跨过”关键点：对于一种无向图上的方案，若不跨过关键点，则必定可以在有向图上完成。

可以证明，可以跨过关键点的充要条件是指向关键点的两条边都被经过。所以只用存这两条边的状态即可。我们称这两条边为“关键边”。

特殊情况下，一个环不由两条方向相反的链组成，而是所有边方向相同，则认为 $1$ 号点所在的树的根是关键点；只有一条关键边，则认为另一条关键边已经被经过。与一般情况处理方法相同。

时间复杂度 $\mathcal O(n^2)$。

Subtask 3：

由于起点 $i$ 与终点 $i+1$ 已定，我们考虑直接求出最优的路径。对于树，最优路径长度就是两点的深度之和减两倍的最近公共祖先的深度；对于环，由于只与是否经过两条关键边相关，所以转移最多有四种情况：不经过关键边、经过某一条关键边、经过两条关键边。

若经过了一条关键边并且经过了起点与终点的其中一个点两次，则可以看做先进行了一次不经过关键边的转移，再进行一次从一个点到关键边再回来的转移。后者与另一个点无关，可以在转移前或后考虑。

若经过了一条关键边但起点与终点均只经过一次，那么一定经过了关键点，即要么起点与终点之一是关键点，要么跨过了关键点，此时两条关键边均被经过。

所以特判起点和终点是关键点的情况，否则就只有两种情况：不经过关键边和经过两条关键边，即不经过关键点和经过关键点。分类讨论即可。具体写法可以参考代码。

复杂度 $\mathcal O(n\log n)$。瓶颈在求 LCA，所以理论可以做到 $\mathcal O(n)$。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
typedef long long ll;
bool Mbe;
inline int read() {
	int res=0; char ch;
	do ch=getchar(); while(!isdigit(ch));
	do res=res*10+(ch^48); while(isdigit(ch=getchar()));
	return res;
}
template <typename T>
inline void to_min(T &x, const T y) {
	if(x>y) x=y;
}
template <typename T>
inline T min_(const T x, const T y) {
	return x<y? x: y;
}
const int mN=5e5+9, mD=20;
int n;
int oe=1, head[mN], e[mN*2][2];
inline void add(const int x, const int y) {
	e[++oe][0]=head[x], e[head[x]=oe][1]=y;
}

bool vis[mN];
int m, r[mN], key_r, a[mN];
/*
r, a 均用来存环上节点编号
key_r 为关键点
如果 key_r=0 则关键点为 1 号点对应的根节点，且边方向为 r[1]->r[m]
否则边方向为 r[1]->r[key_r]<-r[m]
*/
bool dfs_r(int x, int f) {	//找环
	bool res=0;
	vis[x]=1;
	for(int t=head[x], y; y=e[t][1], t; t=e[t][0]) if(y && y!=f) {
		if(vis[y] || dfs_r(y, x)) {
			e[t][1]=e[t^1][1]=0, res=1;
			r[++m]=y;
			if(!key_r && !(t&1)) key_r=m;
		}
	}
	return res && x!=r[1];
}
int d[mN], fa[mN][mD], col[mN];
void dfs_pre(int x, int c) {	//染色并预处理 LCA 数组
	col[x]=c;
	for(int t=1; fa[x][t-1]; ++t) fa[x][t]=fa[fa[x][t-1]][t-1];
	for(int t=head[x], y; y=e[t][1], t; t=e[t][0]) if(y && y!=fa[x][0]) {
		fa[y][0]=x, d[y]=d[x]+1, dfs_pre(y, c);
	}
}
int cal_lca(int x, int y) {
	if(d[x]<d[y]) swap(x, y);
	for(int t=mD-2; ~t; --t) if(d[fa[x][t]]>=d[y]) x=fa[x][t];
	if(x==y) return x;
	for(int t=mD-2; ~t; --t) if(fa[x][t]^fa[y][t]) x=fa[x][t], y=fa[y][t];
	return fa[x][0];
}

ll dp[mN][2][2];
//第一维表示阶段，第二、三维表示是否经过左、右侧的关键边。


bool Men;
int main() {
	cerr<<"memory: "<<(&Mbe-&Men>>20)<<" MB\n";

	n=read();
	rep(__, 1, n) {
		int x=read(), y=read();
		add(x, y), add(y, x);
	}
	dfs_r(1, 0);

	if(key_r) {
		//使得关键点位于 m，这样不经过关键点的路径一定在 [1,m) 内。
		a[0]=r[key_r];
		rep(i, 1, m-key_r) a[i]=r[i+key_r];
		rep(i, m-key_r+1, m) a[i]=r[i-(m-key_r)];
	} else {
		a[0]=a[m]=r[1];
		rep(i, 1, m-1) a[i]=r[i+1];
	}
	d[0]=-1;
	if(!key_r) {
		rep(i, 0, m-1) dfs_pre(a[i], i);
	} else {
		rep(i, 1, m) dfs_pre(a[i], i);
	}

	int stp=1;
	ll ans=0, det=0;
	//det 表示树上的答案，ans 表示环上的答案
	memset(dp, 0x3f, sizeof dp);
	dp[1][0][0]=0;
	dp[1][1][0]=2*col[1], dp[1][0][1]=2*(m-col[1]);

	rep(i, 2, n) {
		if(col[i]==col[i-1]) {	//树
			det+=d[i]+d[i-1]-2*d[cal_lca(i-1, i)];
			printf("%lld\n", det+ans);
		} else {	//环
			det+=d[i]+d[i-1];
			++stp;
			rep(t0, 0, 1) rep(t1, 0, 1) {
				int u=col[i-1], v=col[i];
				const ll z=dp[stp-1][t0][t1];
				if(u==m) {	//如果起点是 m
					if(!t0 && !t1) continue;	//两条关键边均未经过
					if(!t1) u=0;	//未经过右侧关键边，则把起点放在左侧。
				}
				if(v==m) {	//如果终点是 m
					to_min(dp[stp][t0][1], z+m-u);	//走右侧
					to_min(dp[stp][1][t1], z+u);	//走左侧
				} else {
					to_min(dp[stp][t0][t1], z+abs(u-v));	//不经过关键点
					if(u<v && t1 || u>v && t0) {	//经过关键点
						to_min(dp[stp][1][1], z+m-abs(u-v));
					}
				}
			}
			if(col[i]^m) rep(t, 0, 1) {	//到关键边再回来
				to_min(dp[stp][1][t], dp[stp][0][t]+2*col[i]);
				to_min(dp[stp][t][1], dp[stp][t][0]+2*(m-col[i]));
			}
			printf("%lld\n", det+(ans=min_(min_(dp[stp][0][0], dp[stp][0][1]),
			min_(dp[stp][1][0], dp[stp][1][1]))));
		}
	}
	return 0;
}