一遍dfs找到1节点需要装换的边数,然后再一次dfs求得每个点的值,若i能到j,则dp[j]=dp[i]+1,否则dp[j]=dp[i]-1。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<iostream> using namespace std; vector<int> tree[200005]; vector<int> dir[200005]; int dp[200005]; int dfs1(int now,int fa=-1) { int tot=0; for(int i=0;i<tree[now].size();i++) { int to=tree[now][i]; if(to!=fa) { tot+=(dfs1(to,now)+(dir[now][i]<0?1:0)); } } return tot; } void dfs2(int now,int tot,int fa=-1) { dp[now]=tot; for(int i=0;i<tree[now].size();i++) { int to=tree[now][i]; if(to!=fa) { dfs2(to,tot+dir[now][i],now); } } } int main() { int n; while(~scanf("%d",&n)) { int a,b; for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); tree[a].push_back(b); tree[b].push_back(a); dir[a].push_back(1); dir[b].push_back(-1); } int t=dfs1(1); dfs2(1,t); int mins=3000000; for(int i=1;i<=n;i++) mins=min(dp[i],mins); printf("%d\n",mins); for(int i=1;i<=n;i++) { if(dp[i]==mins) { printf("%d ",i); } } puts(""); } return 0; }