自动搬运

查看原文

来自洛谷，原作者为

	diqiuyi heaksicn你真唐吧

搬运于2025-08-24 23:04:10，当前版本为作者最后更新于2025-01-26 16:50:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门。

下文默认 $\sum m_i$ 和 $n$ 同阶。

容易证明当一个子树内最小值固定时，最大值越小越好。所以不妨设 $g_{x,i}$ 表示 $x$ 子树内最小值为 $i$ 时最大值的最小值（可以看成维护区间）。对每个点枚举全排列更新答案可以做到 $O(n^2k!)$。

考虑优化，显然每个点的答案可以用状压来计算。设 $f_{x,i,S}$ 表示考虑了 $S$ 内的子树的答案。此时转移是容易的，可以做到 $O(n^22^kk)$。

此时状态已经不好优化，这个东西也没法用数据结构维护，所以考虑观察性质。一个显然的事情就是若存在 $l1\le l2\le r2\le l1$，那么 $[l1,r1]$ 这个状态就是无用的。我们可以考虑对于每个点只保留有用的状态，记 $x$ 子树内的状态为 $S_x$。则复杂度为 $O(\sum |S_i|(2^kk+\log n))$，$\log n$ 是因为要排序。

另一个优化是若 $x$ 的儿子只有一个，那么就不需要管它。

接下来我们要证明 $\sum |S_i|$ 是 $O(n\log n)$ 的。

对于一个点 $x$，设 $x$ 的儿子为 $c_1,\cdots,c_k(k\ge2)$。记它 $|S|$ 最大的点为 $v$。显然 $S_x$ 中的每一个区间的 $2$ 端来自不同的子树，又因为每个区间最多出现在端点处 $2$ 次（分别作为起点和终点），所以有 $|S_x|\le 2(\sum |S_{c_i}|-|S_v|)$。

显然 $|S_x| \le \sum |S_{c_i}|$。

考虑类似启发式合并的证明。若 $2|S_v|\le\sum |S_{c_i}|$，则每个区间在贡献一次后大小都至少乘 $2$，最多贡献 $\log n$ 次。否则可以看成是除了最大值以外的点都至少乘 $2$，而最大值只往上走了 $\sum |S_{c_i}|-|S_v|$，这一部分大小也乘了 $2$，所以每个点还是最多贡献 $\log n$ 次。

所以总的时间复杂度为 $O(n\log n(2^kk+\log n))$，不满。实现的时候要特别注意只有一个儿子的情况。

输出方案是简单的。

code

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define uint unsigned int
#define pii pair<int,int>
#define io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
inline int read(){
	int x=0;bool f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return f?x:-x;
}
int n,dp[256],lst[256],vs[256],top,now,cnt,l[100005],r[100005],ans[100005];
pii v[100005],stk[100005],zpd[50000000];
vector<int> g[100005],ord[100005];
void dfs(int x){
	if(!g[x].size()) return ;
	for(int y:g[x])
		dfs(y);
	if(g[x].size()==1) return l[x]=l[g[x][0]],r[x]=r[g[x][0]],void();
	for(int y:g[x])
		for(int i=l[y];i<=r[y];i++)
			ans[zpd[i].first]=114514;
	int cntv=0;top=0;
	for(int i=0;i<g[x].size();i++)
		for(int j=l[g[x][i]];j<=r[g[x][i]];j++){
			auto z=zpd[j];
			memset(dp,63,sizeof(dp));
			dp[1<<i]=z.second;
			for(int s=0;s<(1<<g[x].size());s++)
				if(s&(1<<i))
					for(int j=0;j<g[x].size();j++)
						if(j!=i&&(s&(1<<j))){
							int pos=lower_bound(zpd+l[g[x][j]],zpd+r[g[x][j]]+1,(pii){dp[s^(1<<j)],0})-zpd;
							if(pos!=r[g[x][j]]+1)
								dp[s]=min(dp[s],zpd[pos].second);
						}
			if(dp[(1<<g[x].size())-1]<ans[z.first])
				ans[z.first]=dp[(1<<g[x].size())-1];
		}
	for(int y:g[x])
		for(int i=l[y];i<=r[y];i++){
			auto z=zpd[i];
			if(ans[z.first]<114514)
				v[++cntv]={z.first,ans[z.first]},ans[z.first]=114514;
		}
	sort(v+1,v+cntv+1);
	for(int i=1;i<=cntv;i++){
		pii y=v[i];
		while(top&&stk[top].second>=y.second) top--;
		stk[++top]=y;
	}
	l[x]=now+1;
	for(int i=1;i<=top;i++) zpd[++now]=stk[i];
	r[x]=now;
} 
void solve(int x,int p){
	if(!g[x].size()) return ord[x].push_back(zpd[p].first);
	if(g[x].size()==1) return ord[x].push_back(g[x][0]),solve(g[x][0],p);
	for(int y:g[x])
		for(int i=l[y];i<=r[y];i++)
			ans[zpd[i].first]=114514;
	int cntv=0;top=0;
	for(int i=0;i<g[x].size();i++)
		for(int j=l[g[x][i]];j<=r[g[x][i]];j++){
			auto z=zpd[j];
			if(z.first!=zpd[p].first) continue;
			memset(dp,63,sizeof(dp));
			dp[1<<i]=z.second,lst[1<<i]=i,vs[1<<i]=j;
			for(int s=0;s<(1<<g[x].size());s++)
				if(s&(1<<i))
					for(int j=0;j<g[x].size();j++)
						if(j!=i&&(s&(1<<j))){
							int pos=lower_bound(zpd+l[g[x][j]],zpd+r[g[x][j]]+1,(pii){dp[s^(1<<j)],0})-zpd;
							if(pos!=r[g[x][j]]+1&&zpd[pos].second<dp[s])
								dp[s]=zpd[pos].second,lst[s]=j,vs[s]=pos;
						}
			if(dp[(1<<g[x].size())-1]==zpd[p].second){
				int s=(1<<g[x].size())-1;
				vector<int> vv;vv.clear();
				while(s) ord[x].push_back(g[x][lst[s]]),vv.push_back(vs[s]),s^=(1<<lst[s]);
				for(int i=0;i<vv.size();i++)
					solve(ord[x][i],vv[i]);
				reverse(ord[x].begin(),ord[x].end());
				return ;
			}
		}
}
int main(){
	n=read();
	for(int i=1,x;i<=n;i++){
		x=read();
		if(x==1){
			x=read();
			for(int j;x--;)
				j=read(),g[i].push_back(j);
		}
		else{
			x=read();
			l[i]=now+1;
			for(int j;x--;)
				j=read(),zpd[++now]={j,j};
			r[i]=now;sort(zpd+l[i],zpd+r[i]+1);
		}
	}
	dfs(1);
	if(r[1]>=l[1]){
		cout<<"Yes\n";
		solve(1,l[1]);
		for(int i=1;i<=n;i++,cout<<'\n')
			for(int x:ord[i])
				cout<<x<<' ';
	}
	else cout<<"No\n";
    return 0;
}