fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 100000 + 5;
  5.  
  6. int n;
  7. vector<int> gph[MAXN];
  8. int parent_[MAXN], depth_[MAXN];
  9. int heavy[MAXN], height_[MAXN];
  10. long long baseVal[MAXN], costNode[MAXN];
  11.  
  12. int ceil_log2_int(int x){              // ceil(log2 x), x >= 1
  13.     if (x <= 1) return 0;
  14.     return 32 - __builtin_clz(x - 1); // cho int 32-bit
  15. }
  16. inline long long G(int L){             // g(L)
  17.     if (L == 0) return 0;
  18.     return 1 + ceil_log2_int(L);
  19. }
  20.  
  21. void dfs_height(int u, int p){
  22.     parent_[u] = p;
  23.     heavy[u] = -1;
  24.     int bestH = -1, bestChild = -1;
  25.     for (int v : gph[u]) if (v != p){
  26.         depth_[v] = depth_[u] + 1;
  27.         dfs_height(v, u);
  28.         if (height_[v] > bestH){
  29.             bestH = height_[v];
  30.             bestChild = v;
  31.         }
  32.     }
  33.     height_[u] = (bestH == -1 ? 0 : bestH + 1);
  34.     heavy[u] = bestChild; // **chọn con có height lớn nhất**
  35. }
  36.  
  37. void decompose_from_head(int h){
  38.     int u = h, d = 0;
  39.     while (u != -1){
  40.         costNode[u] = baseVal[h] + G(d);
  41.  
  42.         // rẽ qua các cạnh nhẹ
  43.         for (int v : gph[u]) if (v != parent_[u] && v != heavy[u]){
  44.             baseVal[v] = costNode[u] + 1; // trả 1 cho cạnh nhẹ
  45.             decompose_from_head(v);       // head mới
  46.         }
  47.         u = heavy[u]; // tiếp tục xuống con nặng
  48.         d++;
  49.     }
  50. }
  51.  
  52. int main(){
  53.     ios::sync_with_stdio(false);
  54.     cin.tie(nullptr);
  55.  
  56.     int T; 
  57.     if (!(cin >> T)) return 0;
  58.     while (T--){
  59.         cin >> n;
  60.         for (int i = 1; i <= n; ++i){
  61.             gph[i].clear();
  62.             baseVal[i] = costNode[i] = 0;
  63.         }
  64.         for (int i = 0; i < n - 1; ++i){
  65.             int u, v; cin >> u >> v;
  66.             gph[u].push_back(v);
  67.             gph[v].push_back(u);
  68.         }
  69.  
  70.         depth_[1] = 0;
  71.         dfs_height(1, 0);      // chọn heavy = con cao nhất
  72.         baseVal[1] = 0;
  73.         decompose_from_head(1); // tính cost mọi nút
  74.  
  75.         long long ans = 0;
  76.         for (int i = 1; i <= n; ++i) ans = max(ans, costNode[i]);
  77.         cout << ans << '\n';
  78.     }
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 8456KB
comments (?)
stdin
copy 
3
17
1 2
1 3
2 4
2 5
2 6
3 7
3 8
4 9
4 10
6 11
7 12
8 13
13 14
13 15
14 16
16 17
12
1 2
2 4
4 5
5 6
4 7
1 3
3 8
8 9
3 10
10 11
10 12
2
1 2
stdout
copy 
4
3
1
https://ideone.com/agX1tx
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!