自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

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

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

以下是正文

我好像秒了。

分析

<0> 记 $q_i$ 为 $p_i$ 的逆排列。则显然地，一种填数方式合法当且仅当对于每个节点 $i$ 都有 $q_{a_i}=\min\limits_{j\in\text{subtree}_i}\{q_{a_j}\}$。

<1> 对于最小化字典序问题，显然要从前往后逐位确定。那么我们需要解决的问题变为，在 $q_{a_j(j<i)}$ 均已确定的情况下，求出 $p_{q_{a_i}}$ 可能的最小值。那么：

1. 首先考虑判定，即判断 $q_{a_i}$ 是否可以为 $k$：

   记 $lim_i$ 表示 $i$ 所有已确定的祖先 $j$ 中 $q_{a_j}$ 的最大值。由于题目保证 $fa_i(fa_i<i)$ 已被确定，那么只需满足三个要求，一是需要 $\forall j<i,\ k\neq q_{a_j}$，二是需要 $k>lim_i$，三是需要能够把 $[lim_i+1,k-1]$ 这些球全都填到 $i$ 子树外面。

   对于第三个要求，我们注意到这些球显然能填就填，那么类似拓扑排序地，对于每个祖先均被填过的 $j (j\neq i)$，在处理到第 $lim_j$ 个球时将其加入队列，容易做到 $O(n)$ 判定。

2. 观察结论：

   由判定过程可知，$q_{a_i}$ 的可能值是一段区间 $[l,r]$（再去掉已被使用过的 $q_{a_j} (j<i)$），其中 $l=lim_i+1$，我们只需快速求出区间右端点 $r$。

3. 观察结论：

   考虑这样一种刻画。记录 $cnt_i=\sum\limits_{j\notin \text{subtree}_i} [lim_j=i]$ 及其前缀和数组 $sum_i$，则可以确定 $r=\min\{i|sum_i<i\}$。

   证明：一方面，$sum_i<i$ 意味着第 $i$ 个球一定无处可填，即 $r\leq i$；另一方面，当 $\forall j<i,\ sum_j\geq j$ 时，由于题目保证 $\forall x<y,dep_x \leq dep_y$（已确定的点一定形成包含根的连通块），对子树外未确定的点按照 $(lim,dep)$ 双关键字排序后依次填入球一定合法，因此 $r=i$。

4. 那么此时可以做到 $O(n)$ 时间确定一位，总复杂度 $O(n^2)$。

<2> 考虑优化。目前的时间复杂度瓶颈有两处，分别是求右端点 $r$ 和区间求未被选择的数的 $\min$。

1. 后者可以使用线段树简单处理。只需单点修改（每次把被选择的数改成充分大的数）+区间求 $\min$，时间复杂度 $O(n\log n)$。

2. 前者可以利用题目条件。注意到题目保证 $\forall x<y,dep_x\leq dep_y$，这意味着每次确定一个数时，其子树内所有点的 $lim$ 均相同。因此对权值考虑，维护 $sum_i-i$，只需支持“后缀加减，求第一个值为负数的下标”，可以在维护区间加区间 $\min$ 的线段树上二分实现，时间复杂度 $O(n\log n)$。

3. 综上，总时间复杂度 $O(n\log n)$，可以通过本题。

代码

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long

int n,u,v,fa[500005],dep[500005],sz[500005],ans[500005];
int pp[500005],usd[500005],wz[500005];
vector <int> e[500005];

void dfs0(int x,int fat)
{
	sz[x]=1;
	for(auto i:e[x])
	{
		if(i==fat) continue;
		dep[i]=dep[x]+1; fa[i]=x; dfs0(i,x); sz[x]+=sz[i];
	}
}

struct tree1
{
	pair<int,int> mn;
}tree1[2000005];

#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define m(x) tree1[x].mn
#define md(x,y) ((x+y)>>1)
#define push_up1(x) m(x)=min(m(ls(x)),m(rs(x)))

void build1(int l,int r,int p)
{
	if(l==r) return m(p)=mp(pp[l],l),void(); int mid=md(l,r);
	build1(l,mid,ls(p)); build1(mid+1,r,rs(p)); push_up1(p);
}
void cz1(int l,int r,int x,int p)
{
	if(l==r) return m(p)=mp(10000000,l),void(); int mid=md(l,r);
	if(mid>=x) cz1(l,mid,x,ls(p)); else cz1(mid+1,r,x,rs(p)); push_up1(p);
}
pair<int,int> ask1(int l,int r,int x,int y,int p)
{
	if(l>=x&&r<=y) return m(p); int mid=md(l,r); pair<int,int> na=mp(10000000,0);
	if(mid>=x) na=min(na,ask1(l,mid,x,y,ls(p))); if(mid<y) na=min(na,ask1(mid+1,r,x,y,rs(p))); return na;
}

struct tree2
{
	int mn,tagadd;
}tree2[2000005];

#define n(x) tree2[x].mn
#define push_up2(x) n(x)=min(n(ls(x)),n(rs(x)));
#define tg(x) tree2[x].tagadd

void cza(int k,int p) {n(p)+=k; tg(p)+=k;}
void push_down(int p) {cza(tg(p),ls(p)); cza(tg(p),rs(p)); tg(p)=0;}

void build2(int l,int r,int p)
{
	if(l==r) return n(p)=n-l,void(); int mid=md(l,r);
	build2(l,mid,ls(p)); build2(mid+1,r,rs(p)); push_up2(p);
}
void cza(int l,int r,int x,int y,int k,int p)
{
	if(l>=x&&r<=y) return cza(k,p),void(); int mid=md(l,r); push_down(p);
	if(mid>=x) cza(l,mid,x,y,k,ls(p)); if(mid<y) cza(mid+1,r,x,y,k,rs(p)); push_up2(p);
}
int ask2(int l,int r,int p)
{
	if(l==r) return l; int mid=md(l,r); push_down(p);
	if(n(ls(p))<0) return ask2(l,mid,ls(p)); else return ask2(mid+1,r,rs(p));
}

/*int cnt[500005]; 这是赛时用来验证正确性的暴力。
void dfs1(int x,int fat,int lim)
{
	lim=max(lim,wz[x]);
	cnt[lim]++;
	for(auto i:e[x])
	{
		if(i==fat) continue;
		dfs1(i,x,lim);
	}
}
int calc(int x)
{
	wz[x]=n+1;
	for(int i=1;i<=n;i++) cnt[i]=0;
	dfs1(1,1,1);
	for(int i=1;i<=n;i++)
	{
		cnt[i]+=cnt[i-1]; if(cnt[i]<i) return i;
	}
	return n;
}*/
void solve(int x)
{
	if(x==1) {return ans[x]=pp[1],wz[x]=1,usd[1]=1,cz1(1,n,1,1),void();}
	int nl=wz[fa[x]];
	cza(1,n+1,wz[fa[x]],n+1,-sz[x],1);
	cza(1,n+1,n+1,n+1,sz[x],1);
	int nr=ask2(1,n+1,1);
	pair<int,int> na=ask1(1,n,nl,nr,1);
	ans[x]=pp[na.se],wz[x]=na.se,usd[na.se]=1,cz1(1,n,na.se,1);
	cza(1,n+1,n+1,n+1,-sz[x],1);
	cza(1,n+1,na.se,n+1,sz[x],1);
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>pp[i];
	for(int i=1;i<=n-1;i++) cin>>u>>v,e[u].pb(v),e[v].pb(u);
	dfs0(1,1);
	build1(1,n,1);
	build2(1,n+1,1);
	for(int i=1;i<=n;i++) solve(i);
	for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl;
}