【题解】P7807 「DCOI2021」C 魔力滋生

部分分提示正解：前两个 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');
}