1 /* 2 题意：求一个点为根节点，使得到其他所有点的距离最短，是有向边，反向的距离+1 3 树形DP：首先假设1为根节点，自下而上计算dp[1](根节点到其他点的距离)，然后再从1开始，自上而下计算dp[v], 4 此时可以从上个节点的信息递推出来 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <cmath> 9 #include <vector> 10 using namespace std; 11 12 const int MAXN = 2e5 + 10; 13 const int INF = 0x3f3f3f3f; 14 struct Edge { 15 int v, w; 16 }; 17 vector<Edge> G[MAXN]; 18 int dp[MAXN]; 19 bool vis[MAXN]; 20 int n, res; 21 22 void DFS(int u) { 23 vis[u] = true; 24 for (int i=0; i<G[u].size (); ++i) { 25 int v = G[u][i].v, w = G[u][i].w; 26 if (vis[v]) continue; 27 DFS (v); 28 res += w; 29 } 30 } 31 32 void DFS2(int u) { 33 vis[u] = true; 34 for (int i=0; i<G[u].size (); ++i) { 35 int v = G[u][i].v, w = G[u][i].w; 36 if (vis[v]) continue; 37 if (w == 0) dp[v] = dp[u] + 1; 38 else dp[v] = dp[u] - 1; 39 DFS2 (v); 40 } 41 } 42 43 void work(void) { 44 memset (vis, false, sizeof (vis)); 45 memset (dp, 0, sizeof (dp)); 46 47 res = 0; DFS (1); dp[1] = res; 48 memset (vis, false, sizeof (vis)); 49 DFS2 (1); 50 51 int mn = INF, p = 0; 52 for (int i=1; i<=n; ++i) { 53 if (mn >= dp[i]) { 54 mn = dp[i]; p = i; 55 } 56 } 57 printf ("%d\n", mn); 58 for (int i=1; i<=n; ++i) { 59 if (i == p) { 60 printf ("%d\n", i); break; 61 } 62 if (dp[i] == mn) printf ("%d ", i); 63 } 64 } 65 66 int main(void) { //Codeforces Round #135 (Div. 2) D. Choosing Capital for Treeland 67 // freopen ("A.in", "r", stdin); 68 69 while (scanf ("%d", &n) == 1) { 70 for (int i=1; i<=n; ++i) G[i].clear (); 71 for (int i=1; i<=n-1; ++i) { 72 int u, v; scanf ("%d%d", &u, &v); 73 G[u].push_back ((Edge) {v, 0}); 74 G[v].push_back ((Edge) {u, 1}); 75 } 76 77 work (); 78 } 79 80 return 0; 81 }
