自动搬运

查看原文

来自洛谷，原作者为

	xiaoqian02 小舟从此逝，江海寄余生。

搬运于2025-08-24 22:44:16，当前版本为作者最后更新于2023-02-01 19:33:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

刚打完比赛，来水个题解。

这篇题解讲 dfs 做法，但是我觉得应该也有 bfs 做法。

个人认为这篇题解还算比较好理解。

第一部分：思路

这道题我一直以为从任意点开始走都可以，于是耗了 $15$ 分钟，直到同学提醒我……

既然只能从 $1$ 开始，就好办一点。

首先，我们知道，一定不能经过权值为 $-1$ 的点。因为如果在第 $k$ 个点经过 $-1$，一定有 $\sum\limits_{j=k+1}^{|P|} \frac{1}{2^{j-1}} + ( - \frac{1}{2^{k-1}}) < 0$。不可能经过无穷多个点，取不到等号，反而亏了。

就这样，一个 $-1$ 毁掉了一切。

所以，只能走 $1$ 或 $0$。感谢良心的出题人与良心的小 L，没有搞出乱七八糟的权值。

同时，我们也能证明能走 $1$ 时走 $1$ 一定比走 $0$ 优。而且根据题目里字典序的定义，最后不能有多余的 $0$，否则去掉了字典序更小。

直接这么写，其实 Subtask $5$ 就过了。但我们的目标不是 $20$ 分，而是 $100$ 分。

由于这道题的字典序比较坑，所以我们不用链式前向星，而是用 vector 来存边（邻接表）。存完边排个序就可以了。

具体 dfs 的过程写在 dfs 代码注释里（应该算比较详细了）。

bool dfs(int p,int fr,int dep)
//由于建了双向边，fr 存从哪里过来的，避免再回去
//dep 存深度，便于修改 qz 数组
//a 是权值，ed 是边（用 vector 存），nxt 存下一个怎么走最大（为 0 表示停下来最大），qz 是当前最大值（二进制）
//mx 存储从当前点出发能到的点权值的最大值，便于控制接下来全是 0 的情况
//dfs 函数是 bool 类型因为要存下来走这一条有没有更新最大值，如果更新了就要把 nxt 连过去。bg 就是存有没有更新的
{
	int mx=-1;
	bool bg=0;
	for(int i=0;i<ed[p].size();i++)
	{
		int k=ed[p][i];
		if(k==fr) continue;
		mx=max(mx,a[k]);
		if(a[k]==-1) continue;//-1 一定不走
		if(a[k]==1)//能走 1 一定走 1
		{
			if(qz[dep]==0)
			{
				if(mxd<dep) mxd=dep;//更新一下长度，便于之后再更新时清零
				qz[dep]=1;
				nxt[p]=k;//连过去
				bg=1;//能更新
				for(int j=dep+1;j<=mxd;j++) qz[j]=0;//后面全部清零
			}
			bool pp=dfs(k,p,dep+1);//这条路下去有没有更新
			if(pp) nxt[p]=k,bg=1;//更新了就连过去
		}
	}
	if(mx==-1) return 0;//走不下去了
	if(mx==0)
	{
		if(qz[dep]==1) return 0;//最大值能取到 1 但是接下来只有 0
		for(int i=0;i<ed[p].size();i++)
		{
			int k=ed[p][i];
			if(k==fr) continue;
			if(a[k]==-1) continue;
			bool pp=dfs(k,p,dep+1);
			if(pp) nxt[p]=k,bg=1;
		}
	}
	return bg;
}

dfs 结束之后还要特判。

• 如果 $a_1=-1$，后面是怎么加都加不到 $0$ 的。所以我们什么都不干，直接 return 0; 就可以了。这个其实应该在 dfs 前判断，但因为也是特判，所以放到这里一起说。

• 如果 $a_1=0$ 且 $nxt_i=0$，说明只走到 $1$ 最优，当然这等同于什么都不干，所以也不输出。

最后输出一下，就能愉快地 AC 了。

第二部分：完整代码

dfs 部分前面给过，这一段就不加注释了。

#include<bits/stdc++.h>
using namespace std;
void IOS()//cin 优化
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
vector<int> ed[500005];
//vector 存边
//P.S.本蒟蒻之前从来没用过 vector，这次是第一次
int n,u,v,mxd,a[500005],nxt[500005];
int qz[500005];
bool vis[500005];
bool dfs(int p,int fr,int dep)
{
	int mx=-1;
	bool bg=0;
	for(int i=0;i<ed[p].size();i++)
	{
		int k=ed[p][i];
		if(k==fr) continue;
		mx=max(mx,a[k]);
		if(a[k]==-1) continue;
		if(a[k]==1)
		{
			if(qz[dep]==0)
			{
				if(mxd<dep) mxd=dep;
				qz[dep]=1;
				nxt[p]=k;
				bg=1;
				for(int j=dep+1;j<=mxd;j++) qz[j]=0;
			}
			bool pp=dfs(k,p,dep+1);
			if(pp) nxt[p]=k,bg=1;
		}
	}
	if(mx==-1) return 0;
	if(mx==0)
	{
		if(qz[dep]==1) return 0;
		for(int i=0;i<ed[p].size();i++)
		{
			int k=ed[p][i];
			if(k==fr) continue;
			if(a[k]==-1) continue;
			bool pp=dfs(k,p,dep+1);
			if(pp) nxt[p]=k,bg=1;
		}
	}
	return bg;
}
int main()
{
	IOS();
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		ed[u].push_back(v);
		ed[v].push_back(u);
	}
	for(int i=1;i<=n;i++) sort(ed[i].begin(),ed[i].end());//排个序，方便按字典序来
	if(a[1]==-1) return 0;
	dfs(1,-1,0);
	if(a[1]==0&&!nxt[1]) return 0;
	for(int i=1;i;i=nxt[i]) cout<<i<<" ";
	cout<<endl;
	return 0;
}

第三部分：Others

这个小 L 确实很无聊

std 看起来好长啊

这题的数据需要加强一下，不然可以用可以过大多数数据的错解面向数据编程，然后过这道题。

有依赖的捆绑挺好的，有些错解大数据能过但小数据过不去，导致最后 $20$ 分。

最后，如果你的代码过不去，给一组可能的 hack（至少 hack 掉了同机房的同学）：

Input:
10
0 0 0 0 0 1 0 0 0 1
1 2
2 3
3 4
4 5
5 6
1 7
7 8
8 9
9 10
Output:
1 7 8 9 10