1 /* 2     题意：求一个点为根节点，使得到其他所有点的距离最短，是有向边，反向的距离+1 3     树形DP：首先假设1为根节点，自下而上计算dp[1](根节点到其他点的距离)，然后再从1开始，自上而下计算dp[v], 4             此时可以从上个节点的信息递推出来 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         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
         
           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
          
           = 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 Treeland67 // 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 }