1 条题解
-
1
#include<bits/stdc++.h> const int Mx=5e5+10; int n,m,fir[Mx],nex[Mx<<1],to[Mx<<1],tot,de[Mx]; struct Edge{int x,y;}E[Mx]; void addEdge(int x,int y){ nex[++tot]=fir[x];fir[x]=tot;to[tot]=y;de[x]++; nex[++tot]=fir[y];fir[y]=tot;to[tot]=x;de[y]++; } int rem[Mx],top; void dfs(int x,int f){ int flag=0; for(int i=fir[x];i;i=nex[i]){ int v=to[i]; if(v==f)continue; dfs(v,x); flag=1; } if(flag==0)rem[++top]=x; } int main(){ scanf("%d",&n); for(int i=1,x,y;i<n;i++){ scanf("%d%d",&x,&y); addEdge(x,y); } int st=0; for(int i=1;i<=n;i++)if(de[i]>1){st=i;break;} if(st==0)return puts("1"),0; dfs(st,0); for(int i=1;i<=top/2;i++)E[++m]=(Edge){rem[i],rem[i+top/2]}; if(top&1)E[++m]=(Edge){rem[1+top/2],rem[top]}; printf("%d\n",m); for(int i=1;i<=m;i++)printf("%d %d\n",E[i].x,E[i].y); }
- 1
信息
- ID
- 3596
- 时间
- 1000ms
- 内存
- 500MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者