cf 218D

n-1개의 변을 주고 dp[i]는 i를 뿌리로 바꾸어야 하는 변수로 i가 임의의 점에 도달할 수 있도록 한다.최소 dp (i) 의 아래 첨자를 오름차순으로 출력합니다.

#include
#include
#include
#include
#include
using namespace std;
const int maxn=2*100000+10,inf=1e9;

struct node
{
    int v,w;
    node(int _v=0,int _w=0)
    {
        v=_v;
        w=_w;
    }
};
vectore[maxn];
vector<int>ans;
int dp[maxn];

void dfs1(int u,int fa)
{
    dp[u]=0;
    for(int i=0;iint v=e[u][i].v,w=e[u][i].w;
        if(v==fa) continue;
        dfs1(v,u);
        dp[u]+=dp[v]+w;
    }
}

void dfs2(int u,int fa)
{
    for(int i=0;iint v=e[u][i].v,w=e[u][i].w;
        if(v==fa) continue;
        dp[v]=dp[u]+(w?-1:1);
        dfs2(v,u);
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            e[i].clear();
            ans.clear();
        }
        for(int i=1;iint u,v;
            scanf("%d %d",&u,&v);
            e[u].push_back(node(v,0));
            e[v].push_back(node(u,1));
        }
        dfs1(1,-1);
        dfs2(1,-1);
        int minn=inf;
        for(int i=1;i<=n;i++)
        minn=min(minn,dp[i]);
        printf("%d
",minn);
        for(int i=1;i<=n;i++)
        {
            if(dp[i]==minn) ans.push_back(i);
        }
        for(int i=0;iif(i1) printf("%d ",ans[i]);
            else printf("%d
",ans[i]);
        }
    }
}