题解：P13346 [EGOI 2025] Laser Strike / 激光突击

题目大意

通信题，给 Alice 一棵树，Alice 需要给出这棵树的一个拓扑序（根任意），并给出传递给 Bob 的额外信息 01 串

s

，要求

|s| \le 1

。

Bob 需要根据额外信息串还原该拓扑序，交互库每次会给出一条树边

(u,v)

，满足

u,v

目前都没被删并且

u,v

中存在一个点是这一步应删的叶子，Bob 需要判断

u,v

哪一个应当被删。

菊花

比较显然，传递第一条边删哪个的信息，剩余每条边与前一条重合的点为根，保留即可。

链

如果只针对该子任务可以想到删与上一条重合的点，但是与菊花做法冲突。

考虑保留菊花做法，那么把链的中点拿出来作根，先花费两个 bit 给出初始两个叶子编号，然后在链两端反复横跳删叶子。

Bob 之所以能识别第三步及之后的叶子，是因为它在之前出现过又不是上一次出现的点，据此判断即可。

然而 2bit 并不节俭，考虑如何消去 1bit。

我们发现这 1 bit 可以通过前两条边的大小关系传递，具体地，为边与边规定一个偏序关系（一个例子是比较

(u,v)

无序对的字典序），如果前两条边的 bit （指叶子较小为 0，叶子较大为 1）相同，则把小的放在前面，否则把大的放在前面，最后传递第一条边的 bit 即可。

Bob 只需判断第二条边与第一条边的大小就知道第二条边的 bit 了。

需要特殊处理点数为偶数情况。

正解

考虑沿用上面的策略。

容易发现 Bob 按以下规则操作：

第一条边：根据额外信息判断。
当前边与上一条边有共点：删掉不共的点。
当前边恰有一个点在之前出现过：删掉该点。

然而依然会存在都不满足的情况，即别处的叶子，对 Bob 来说它的信息是完全未知的，但我们先不管。

假设 Bob 有能力获知「新叶子」的信息，考虑 Alice 如何构造拓扑序使得 Bob 能正确地删空叶子。

首先拉出直径，以中点为根（直径长度奇数时以中间两点为根，即两点深度都为 0）建树，对于非叶结点，如果它的儿子全为叶子，那么它需要一次「新叶子」操作来清空儿子，即先删一个「新叶子」，然后按菊花情况清空儿子。

此时局面上所有原有叶子已经删除，并且将要被删除的叶子都已出现过，我们唯一需要考虑的是不能删完一个点儿子后迅速删除该点，否则会判为菊花情况而把它父亲删掉。

考虑深度从大往小清点，由于选的是直径中点为根，当前层一定有两个以上的点，只有一个是上层最后删去的叶子的父亲，指定它不是下一个被删的点即可。

需要注意的是如果一个叶子被删除，它的兄弟叶子应当被立马删除，因为这样成本最低且保证正确性（指一个非叶点存在非叶儿子，那么非叶儿子被删除时会把叶儿子全部清空，故该点不需要「新叶子」操作）。

最后特判两个根的情况，用菊花的策略即可。

于是我们剩下最后一个问题：Bob 如何获知「新叶子」的信息？

考虑沿用链的策略，即：每出现一个「新叶子」，Bob 会拿它与上一个「新叶子」比较大小，如果上一个「新叶子」更大，则沿用上一个 bit，否则取反。

发现 Alice 的构造也很简单：初始把所有「新叶子」排序，对每个极长相等 bit 段做 reverse 即可。

注意删一个「新叶子」时也要立马清除叶子兄弟，但是这些点并不是「新叶子」。

回顾

总结一下，Alice 的策略是：

先以直径中点（可能是两个）为根建树，按深度分层。

对于非叶节点，如果它儿子全为叶子，提出任意一个儿子作为「新叶子」。

将「新叶子」排序，并 reverse 所有「新叶子」 bit 极长相等段，按序删除。
任意时刻，若上次删除的叶子的父亲有叶儿子，立马删除。
如果当前删除的是该层第一个点，特殊判断该点是不是上次删除叶子的父亲，是的话换一个点删除。
否则任意删除当前层的一点，若删空移至下一层。

最后特殊处理两个根的情况。

Bob 的策略是：

第一条边：用额外信息判断，记为「新叶子」。
和上一条边有共点：删掉不共点。
其中一点出现过：删掉出现过的点。
判断该边与上一条「新叶子」边的大小以获得它的 bit，记该边为「新叶子」。

注意以上策略具有优先级。

代码

CPP

const int N=1e3;
int tp,tot,diam,n,d[N+2],deg[N+2],fa[N+2];
vector<int> e[N+2],f[N+2],g[N+2];
pair<int,int> lst;
bool bz[N+2];
pair<int,int> E(int x,int y) {
	return x<y?make_pair(x,y):make_pair(y,x);
}
void dfs(int u,int p) {
	fa[u]=p;
	for(auto v : e[u]) if(v!=p) {
		++deg[u];
		d[v]=d[u]+1;
		dfs(v,u);
	}
}
pair<int,int> getrt() {
	dfs(0,-1);
	int x=max_element(d,d+n)-d;
	d[x]=0;
	dfs(x,-1);
	int y=max_element(d,d+n)-d;
	diam=d[y];
	for(int i=0; i<diam/2; ++i) y=fa[y];
	if(diam&1) return {fa[y],y};
	return {y,-1};
}
void put(int u) {
	++tot;
	cout<<u<<endl;
	lst={u,fa[u]};
	bz[u]=1;
	if(fa[u]!=-1) {
		if(!--deg[fa[u]]&&fa[fa[u]]!=-1) f[fa[fa[u]]].push_back(fa[u]);
		while(f[fa[u]].size()&&bz[f[fa[u]].back()]) f[fa[u]].pop_back();
		if(f[fa[u]].size()) put(f[fa[u]].back());
	}
}
void solve1() {
	for(int i=0; i<n-1; ++i) {
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	auto [rt,rt1]=getrt();
	memset(deg,0,sizeof(deg));
	d[rt]=0,dfs(rt,rt1);
	fa[rt]=-1;
	if(rt1!=-1) d[rt1]=0,dfs(rt1,rt),fa[rt1]=-1;
	cerr<<"root="<<rt<<","<<rt1<<'\n';
	int maxd=*max_element(d,d+n);
	vector<pair<int,int>> s;
	for(int i=0; i<n; ++i) {
		int c=0;
		for(auto j : e[i]) if(e[j].size()==1) ++c;
		if(e[i].size()>1&&c+1>=e[i].size()) bz[i]=1;
	}
	for(int i=0; i<n; ++i) if(!deg[i]&&fa[i]!=-1) f[fa[i]].push_back(i);
	for(int i=0; i<n; ++i) if(e[i].size()==1) {
		if(!bz[fa[i]]) continue;
		bz[fa[i]]=0;
		s.emplace_back(i,fa[i]);
	}
	sort(s.begin(),s.end(),[](auto x,auto y) { return E(x.fi,x.se)<E(y.fi,y.se); });
	for(int i=0; i<s.size(); ++i) {
		int j=i;
		while(j+1<s.size()&&(s[i].fi<s[i].se)==(s[j+1].fi<s[j+1].se)) ++j;
		reverse(s.begin()+i,s.begin()+j+1);
		i=j;
	}
	cout<<"01"[s[0].fi>s[0].se]<<'\n';
	for(auto [i,j] : s) put(i);
	for(int i=0; i<n; ++i) if(e[i].size()!=1) g[d[i]].push_back(i);
	for(int cur=maxd,lim=n-1-(diam&1); cur>0&&tot<lim; ) {
		while(g[cur].size()&&bz[g[cur].back()]) g[cur].pop_back();
		if(g[cur].empty()) {
			--cur;
			if(!cur) break;
			if(g[cur].back()==lst.se) swap(g[cur].front(),g[cur].back());
			put(g[cur].back());
			continue;
		}
		put(g[cur].back());
	}
	if(diam&1) put(lst.se^rt^rt1);
}
void solve2() {
	static int a[N+2],b[N+2];
	string s;
	cin>>s;
	int x=s[0]=='1';
	pair<int,int> pre;
	for(int i=0; i<n-1; ++i) {
		cin>>a[i]>>b[i];
		if(!i) {
			pre={a[i],b[i]};
			if(x) swap(a[i],b[i]);
		} else if(a[i]==b[i-1]||b[i]==b[i-1]) {
			if(a[i]==b[i-1]) swap(a[i],b[i]);
		} else if(bz[a[i]]||bz[b[i]]) {
			if(bz[b[i]]) swap(a[i],b[i]);
		} else {
			x^=(pre<make_pair(a[i],b[i]));
			pre={a[i],b[i]};
			if(x) swap(a[i],b[i]);
		}
		cout<<a[i]<<endl;
		d[b[i]]=max(d[b[i]],d[a[i]]+1);
		bz[b[i]]=1;
	}
}

题解：P13346 [EGOI 2025] Laser Strike / 激光突击

文章操作

题目大意

菊花

链

正解

回顾

相关推荐

评论

题解：P13346 [EGOI 2025] Laser Strike / 激光突击