CodeForces. 1337C Linova and Kingdom

1.Problem
https://codeforces.com/contest/1337/problem/C

2.Idea
Sort by {Depth - Child Number}, and pick k vertices.

3.Source

 int n, k;  
 vector<int> adj[N];  
 int dist[N];  
 bool visited[N];  
 int child[N];  
 bool col[N];  
 int dist2[N];  
 struct City {  
      int num, child, dist;  
      bool operator < (const City &a)const {  
           return dist - child < a.dist - a.child;  
      }  
 } Cities[N];  
 void getChild(int k)  
 {  
      //cout << k << endl;  
      visited[k] = true;  
      for (int i = 0; i < adj[k].size(); i++) {  
           int u = adj[k][i];  
           if (visited[u] == 0) {  
                getChild(u);  
                child[k] += (1 + child[u]);  
           }  
      }  
 }  
 void colorCities()  
 {  
      for (int i = 0; i < n; i++) {  
           Cities[i].num = i;  
           Cities[i].child = child[i];  
           Cities[i].dist = dist[i];  
      }  
      sort(Cities, Cities + n);  
      for (int i = 0; i < n - k; i++) {  
           int t = Cities[i].num;  
           col[t] = true;  
      }  
 }  
 int main()  
 {  
      cin >> n >> k;  
      for (int i = 0; i < n - 1; i++) {  
           int u, v;  
           cin >> u >> v;  
           u--; v--;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      // get dist  
      memset(visited, 0, sizeof visited);  
      queue<P> q;  
      q.push(P(0, 0));  
      while (!q.empty()) {  
           int v = q.front().first;  
           int d = q.front().second;  
           q.pop();  
           visited[v] = 1;  
           dist[v] = d;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0 && dist[u] == 0) {  
                     q.push(P(u, d + 1));  
                }  
           }  
      }  
      //get child  
      memset(visited, 0, sizeof visited);  
      getChild(0);  
      //color  
      colorCities();  
      //count  
      memset(visited, 0, sizeof visited);  
      queue<P> q1;  
      q1.push(P(0, 0));  
      while (!q1.empty()) {  
           int v = q1.front().first;  
           int d = q1.front().second;  
           q1.pop();  
           visited[v] = 1;  
           dist2[v] = d;  
           if (col[v]) d++;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0) {  
                     q1.push(P(u, d));  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (col[i] == 0) ans += dist2[i];  
      }  
      cout << ans << endl;  
      return 0;  
 }