自动搬运

查看原文

来自洛谷，原作者为

	ainivolAGEM 我们击破的星辰，我们超越的苍穹，我们堕落的星座。

搬运于2025-08-24 23:11:50，当前版本为作者最后更新于2025-07-12 21:53:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前情提要：更好的阅读体验。

题意

题目给出一颗 $N$ 个点的树，要求设计一种方案，在上面添加 $K$ 条边（要求原本不相连），可以将一个点标记，并且将全部点重新编号；然后在这个新图中以之前的信息复原出原树，即删除全部添加的边。

分析

首先，如果重新编号所有点变成图的话我们就无法确认原来的根、叶子之类的节点，所以我们考虑先把所有 $K$ 条边的一端都接在同一个节点上，我们称该节点为“总节点”。但如果直接标记该节点会发现我们无法得知与该点相连的是原来的树还是新加的边。我们尝试以别的方式确认那个点。

我们发现，如果我们把总节点放在一个叶子节点，那么该点相连的边有 $K + 1$ 条，会比较好确认，因为叶子节点是树中相连边最少的点。那么我们标记叶子节点的父亲节点，不仅同时确认总节点的位置也确认哪个是原树边，会是一个比较好的方案。

但其实还有个问题，如果还有一个与标记节点直接相连的点原本也连接了 $K + 1$ 条边的话，我们怎么确认哪个是真的叶子节点呢？考虑以下情况：

• 如果是与总节点同父亲的节点，那么可证明我们必定有比当前总节点深度更大的叶子节点，我们选择深度最大的叶子节点作为总节点就可以让所有同父亲叶子节点都只连 $1$ 条边，也就不可能达到 $K +1$。

• 如果是标记节点的父亲节点，由于 $K \leq 1$，我们可以直接将其中一条新边连接总节点和标记节点的父亲节点，那么我们就可以辨认哪个是总节点了。

还有一个小的误区：对于 $K = 1$ 的情况，如果总节点连接了与其同父亲的另一个节点，那么两者相连边数量一致，如何判断哪个是总节点呢？其实不用判断啊，反正 $K = 1$，只要找出相连的一条新边即可。

AC code

#include<bits/stdc++.h>
#include<utility>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pir;
const int N=304;
ll rt,id,tid,mdep,d[N];
ll tot,head[N];
struct Edge{
	ll to,nxt;
}e[N<<1];
void add_edge(ll u,ll v){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void init(){
	for(int i=1;i<=tot;i++){
		e[i].to=e[i].nxt=0;
	}
	rt=id=tid=mdep=tot=0;
	memset(head,0,sizeof(head));
	memset(d,0,sizeof(d));
}
void dfs(ll u,ll fa,ll dep){
	bool flag=true;
	for(int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if(v==fa){
			d[u]++;
			continue;
		}
		dfs(v,u,dep+1);
		flag=false;
		d[u]++;
	}
	if(flag&&dep>mdep){
		id=u;
		rt=fa;
		mdep=dep;
	}
}
vector<pir> encode_map(ll N,ll K,ll &X,vector<pir> E){
	init();
	for(int i=0;i<E.size();i++){
		add_edge(E[i].first,E[i].second);
		add_edge(E[i].second,E[i].first);
	}
	dfs(1,0,1);
	vector<pir> ans;
	X=rt;
	for(int i=head[rt];i;i=e[i].nxt){
		ll v=e[i].to;
		if(d[v]!=1){
			if(d[v]-1==K){
				ans.push_back(make_pair(v,id));
			}
			tid=v;
		}
	}
	for(int i=1;ans.size()<K;i++){
		if(i!=rt&&i!=id&&i!=tid){
			ans.push_back(make_pair(id,i));
		}
	}
	return ans;
}
vector<pir> decode_map(ll N,ll K,ll X,vector<pir> E){
	init();
	for(int i=0;i<E.size();i++){
		add_edge(E[i].first,E[i].second);
		add_edge(E[i].second,E[i].first);
	}
	for(int i=head[X];i;i=e[i].nxt){
		ll v=e[i].to;
		for(int j=head[v];j;j=e[j].nxt){
			d[v]++;
		}
		if(d[v]-1==K){
			id=v;
		}
	}
	vector<pir> ans;
	for(int i=0;i<E.size();i++){
		if(E[i].first==id||E[i].second==id){
			if(E[i].first!=X&&E[i].second!=X){
				continue;
			}
		}
		ans.push_back(make_pair(E[i].first,E[i].second));
	}
	return ans;
}

一些易错点：

• 在统计与之相连的边数时别忘记考虑根节点。

• 通信题，别写错了，真的。

• 记得初始化。