1 条题解

  • 1
    @ 2022-7-21 21:11:38
    #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
    上传者