自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:09:17，当前版本为作者最后更新于2025-02-15 00:32:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Problem Link

题目大意

给定 $n$ 个点的基环内向树森林，$m$ 条个棋子要从 $u\to v$，每个时刻可以把每个棋子移动到父亲，但同一个格子的棋子只能移动一个，求所有棋子到达的最小时间。

数据范围：$n,m\le 2\times 10^5$。

思路分析

首先我们每轮肯定有限移动距离远终点的点，这样可以得到一个朴素暴力。

但是这个做法无法优化，需要更好地刻画答案，考虑每条边对答案的贡献，即对于每条边 $u\to fa_u$，我们计算所有棋子都离开 $u$ 的最小时刻 $w_u$。

设所有经过这条边的棋子到 $u$ 的距离为 $d_1\sim d_k$（按离开顺序排列），考虑每个棋子离开这条边的时刻 $t_i$，那么有 $t_i\ge \max(d_i,t_{i-1})+1$。

此时 $w_u=\max d_{k-i+1}+i$，显然 $d$ 升序时取到最小。

我们能证明答案恰好能取到下界 $\max w_u$，观察 $w_u$ 的计算，相当于对于一些在 $u$ 的前驱处重合的棋子，我们钦定他们可以一起运动到 $u$ 再考虑重合的问题。

直观上来看这个做法是很对的，因为重合后这两个棋子已经没有本质区别，无论谁先到 $u$ 都是等价的。

即所有经过这条边的棋子的贡献可以正确计算，但有一些不经过 $u$ 的棋子，我们还要考虑他对答案的影响。

对于一条链 $x\to y\to u$，如果有一个棋子从 $x\to y$，那么他在 $x$ 处可能卡住其他到 $u$ 的径棋子

根据我们的朴素贪心，这显然是不可能的，因为经过 $u$ 的棋子剩余距离更大，因此 $x\to y$ 的棋子一定会在这些棋子离开 $x$ 之后再运动，所有这些棋子无影响。

所以我们能证明最优解中，最后一个棋子离开这条边的时刻恰好就是 $w_u$。

那么考虑树的情况，把过 $u$ 的路径用线段树合并，维护每条路径终点的深度，push up 时左边的最大答案加上右边的终点个数，这样就能维护 $w_u$ 了。

然后处理基环树，我们只要让覆盖每条边的棋子集合正确即可。

随便找一条边破环为链，然后把整棵基环树复制一遍接到末尾，如果过 $x\to y$ 路径过环边 $p\to fa_{p}$，就拆成 $x\to p$ 和 $x'\to y$，容易证明此时覆盖每条路径的棋子集合不变。

时间复杂度 $\mathcal O((n+m)\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
struct SegmentTree {
	int tot,ls[MAXN*20],rs[MAXN*20],mx[MAXN*20],ct[MAXN*20];
	void psu(int p) {
		ct[p]=ct[ls[p]]+ct[rs[p]],mx[p]=max(mx[ls[p]]+ct[rs[p]],mx[rs[p]]);
	}
	void ins(int u,int op,int l,int r,int &p) {
		if(!p) p=++tot;
		if(l==r) return ct[p]+=op,mx[p]=(ct[p]?l+ct[p]:0),void();
		int mid=(l+r)>>1;
		u<=mid?ins(u,op,l,mid,ls[p]):ins(u,op,mid+1,r,rs[p]);
		psu(p);
	}
	void merge(int l,int r,int q,int &p) {
		if(!q||!p) return p|=q,void();
		if(l==r) return ct[p]+=ct[q],mx[p]=(ct[p]?l+ct[p]:0),void();
		int mid=(l+r)>>1;
		merge(l,mid,ls[q],ls[p]),merge(mid+1,r,rs[q],rs[p]);
		psu(p);
	}
}	T;
vector <int> G[MAXN],D[MAXN];
int n,m,fa[MAXN],dsu[MAXN],tp[MAXN];
int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
int dcnt,dfn[MAXN],rdn[MAXN],dep[MAXN];
void dfs1(int u) {
	dfn[u]=++dcnt;
	for(int v:G[u]) dep[v]=dep[u]+1,tp[v]=u?tp[u]:v,dfs1(v);
	rdn[u]=dcnt;
}
int op[MAXN],ans,rt[MAXN];
void ins(int x,int y) { ++op[y],D[x].push_back(dep[y]); }
void dfs2(int u) {
	for(int v:G[u]) dfs2(v),T.merge(0,2*n,rt[v],rt[u]);
	T.ins(dep[u],op[u],0,2*n,rt[u]);
	for(int i:D[u]) T.ins(i,-1,0,2*n,rt[u]);
	ans=max(ans,T.mx[rt[u]]-dep[u]);
}
signed main() {
	scanf("%d",&n),iota(dsu+1,dsu+n+1,1);
	for(int i=1;i<=n;++i) scanf("%d",&fa[i]),fa[i+n]=fa[i]+n,dsu[find(i)]=find(fa[i]);
	for(int i=1;i<=n;++i) if(dsu[i]==i) {
		int x=i;
		for(;dsu[x];x=fa[x]) dsu[x]=0;
		fa[x+n]=fa[x],fa[x]=0;
	}
	for(int i=1;i<=2*n;++i) G[fa[i]].push_back(i);
	dfs1(0),scanf("%d",&m);
	for(int x,y;m--;) {
		scanf("%d%d",&x,&y);
		if(dfn[y]<=dfn[x]&&dfn[x]<=rdn[y]) ins(y,x);
		else if(dfn[y]<=dfn[x+n]&&dfn[x+n]<=rdn[y]) ins(y,x+n),ins(tp[y],x);
		else return puts("-1"),0;
	}
	dfs2(0),printf("%d\n",ans);
	return 0;
}