自动搬运

查看原文

来自洛谷，原作者为

	言琢დ “我会成为这里的主宰，清除掉整片土地上的一切障碍，只留下我跟那一堆白骨，她永远不朽，而我不死不灭。”

搬运于2025-08-24 22:33:15，当前版本为作者最后更新于2021-08-15 22:10:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

upd on 2021.10.26：加入代码，删减并修改部分内容。这本身是一篇高赞题解，因此管理员就不用费心再阅读一遍了。

部分分提示正解：前两个 Subtask 一个满足 $x=0$ 另一个满足 $x=1$，提示了分类讨论。

$n$ 个点的树，每个点的度不超过 $2$，也就是说这是一条 链。

首先考虑 $x=0$：显然此时给出的树 $T'$ 即原来的树 $T$，直接读入什么就输出什么即可。

其次考虑 $x=1$：此时每个点连接了一个新建点，但事实上不难发现，这 $n$ 个新建点的度均为 $1$，原来 链 中的点的度至少为 $2$。据此亦不难将所有度为 $1$ 的点从原来的 链 上剥离。

满分做法：树的直径

考虑先找到树的最长链。

若满足 $k=0$，则这条 链 就对应了最大的 $n$。

若满足 $k \ne 0$，则去掉这条 链 的头部和尾部，因为这两个点一定是新建的（否则 $k=0$）

去掉之后的链也一定对应了最大的 $n$。

时间复杂度 $O(n)$，期望得分 $100$ 分。

#include<cstdio>
#include<cstring>
inline int in();
inline void wr(int);
const int N=(int)1e6+5;
struct Node{
	int next,to;
}s[N<<1];int head[N],sLen;
inline void AddEdge(int,int);
inline void dfs(int);
int dep[N],fa[N],q[N];
int main(int argc,char**argv){
#ifndef ONLINE_JUDGE
	freopen(argv[1],"r",stdin);
	freopen(argv[2],"w",stdout);
#endif
	register int m=in(),k=in();
	for(register int i=1;i<m;++i)
		AddEdge(in(),in());
	dfs(1);
	register int root=0;
	for(register int i=1;i<=m;++i)
		if(dep[i]>dep[root])
			root=i;
	memset(dep,0,sizeof(dep));
	memset(fa,0,sizeof(fa));
	dfs(root);
	register int tail=0;
	for(register int i=1;i<=m;++i)
		if(dep[i]>dep[tail])
			tail=i;
	if(m==1){
		wr(1),putchar('\n');
		return 0;
	}
	//only one node
	if(!k){
		while(tail!=root){
			q[++q[0]]=tail;
			tail=fa[tail];
		}
		q[++q[0]]=tail;
		wr(q[0]),putchar('\n');
		for(register int i=1;i<q[0];++i)
			wr(i),putchar(' '),wr(i+1),putchar('\n');
	}
	else{
		tail=fa[tail];
		if(root==tail){
			wr(1),putchar('\n');
			return 0;
		}
		while(fa[tail]!=root){
			q[++q[0]]=tail;
			tail=fa[tail];
		}
		q[++q[0]]=tail;
		wr(q[0]),putchar('\n');
		for(register int i=1;i<q[0];++i)
			wr(i),putchar(' '),wr(i+1),putchar('\n');
	}
}
inline void dfs(int u){
	dep[u]=dep[fa[u]]+1;
	for(register int i=head[u];i;i=s[i].next){
		register int v=s[i].to;
		if(v==fa[u])continue;
		fa[v]=u,dfs(v);
	}
}
inline void AddEdge(int u,int v){
	s[++sLen].next=head[u];
	s[sLen].to=v;head[u]=sLen;
	s[++sLen].next=head[v];
	s[sLen].to=u;head[v]=sLen;
}
inline int in(){
	register char c=getchar();
	register int x=0,f=1;
	for(;c<'0'||c>'9';c=getchar())
		if(c=='-')f=-1;
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c&15);
	return x*f;
}
inline void wr(int x){
	if(x<0)putchar('-'),x=-x;
	if(x/10)wr(x/10);
	putchar(x%10+'0');
}