【题解】「DCOI2021」C 魔力滋生
言琢დ
·
·
题解
upd on 2021.10.26：加入代码，删减并修改部分内容。这本身是一篇高赞题解，因此管理员就不用费心再阅读一遍了。
\rm C~\text{魔力滋生}
部分分提示正解：前两个 Subtask 一个满足 x=0 另一个满足 x=1，提示了分类讨论。
首先考虑 $x=0$：显然此时给出的树 $T'$ 即原来的树 $T$，直接读入什么就输出什么即可。
其次考虑 $x=1$：此时每个点连接了一个新建点，但事实上不难发现，这 $n$ 个新建点的度均为 $1$，原来 **链** 中的点的度至少为 $2$。据此亦不难将所有度为 $1$ 的点从原来的 **链** 上剥离。
**满分做法：树的直径**
考虑先找到树的最长链。
若满足 $k=0$，则这条 **链** 就对应了最大的 $n$。
若满足 $k \ne 0$，则去掉这条 **链** 的头部和尾部，因为这两个点一定是新建的（否则 $k=0$）
去掉之后的链也一定对应了最大的 $n$。
时间复杂度 $O(n)$，期望得分 $100$ 分。
```cpp
#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');
}
```
