Advertisement
Josif_tepe

Untitled

Oct 29th, 2023
868
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <fstream>
  5. using namespace std;
  6. const int maxn = 1e5 + 10;
  7. int n;
  8. vector<int> graph[maxn];
  9. int dfs(int node, int parent) {
  10.     int cows = (int) graph[node].size();
  11.     if(parent == -1) {
  12.         cows++;
  13.     }
  14.    
  15.    
  16.     int cnt_cows = 1, days_to_send = 0;
  17.     while(cnt_cows < cows) {
  18.         cnt_cows *= 2;
  19.         days_to_send++;
  20.     }
  21.     int result = days_to_send;
  22.     for(int neighbour : graph[node]) {
  23.         if(neighbour != parent) {
  24.             result += dfs(neighbour, node) + 1;
  25.         }
  26.     }
  27.     return result;
  28. }
  29. int main() {
  30.     cin >> n;
  31.    
  32.     for(int i = 1; i < n; i++) {
  33.         int a, b;
  34.         cin >> a >> b;
  35.         a--;
  36.         b--;
  37.         graph[a].push_back(b);
  38.         graph[b].push_back(a);
  39.     }
  40.     cout << dfs(0, -1) << endl;
  41.     return 0;
  42. }
  43.  
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement