fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl '\n'
  4. #define PhTrNghia "TASK"
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 2e5 + 5;
  9. const int inf = 1e18;
  10.  
  11. int n, ans;
  12. vector <int> g[maxn];
  13. int deg[maxn], dp[maxn];
  14.  
  15. void dfs (int u, int p){
  16.     int mx1 = 0, mx2 = 0;
  17.  
  18.     for (int v : g[u]){
  19.         if (v == p) continue;
  20.         dfs (v, u);
  21.  
  22.         mx2 = max(mx2, dp[v]);
  23.         if (mx2 > mx1) swap(mx1, mx2);
  24.     }
  25.  
  26.     dp[u] = 0;
  27.  
  28.     if (deg[u] >= 3) dp[u] = 1 + mx1;   
  29.  
  30.     if (deg[u] >= 4) ans = max (ans, mx1 + mx2 + 1);
  31.  
  32.     ans = max (ans, dp[u]);
  33. }
  34.  
  35. signed main(){
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0); cout.tie(0);
  38.     if (fopen(PhTrNghia".INP", "r")){
  39.         freopen(PhTrNghia".INP", "r", stdin);
  40.         freopen(PhTrNghia".OUT", "w", stdout);
  41.     }
  42.  
  43.     int t;
  44.     cin >> t;
  45.  
  46.     while (t--){
  47.         cin >> n;
  48.  
  49.         for (int i = 1; i <= n; i++){
  50.             g[i].clear();
  51.             deg[i] = 0;
  52.             dp[i] = 0;
  53.         }
  54.  
  55.         for (int i = 1; i < n; i++){
  56.             int u, v;
  57.             cin >> u >> v;
  58.             g[u].push_back (v);
  59.             g[v].push_back (u);
  60.             deg[u]++;
  61.             deg[v]++;
  62.         }
  63.  
  64.         ans = 0;
  65.  
  66.         dfs (1, 0);
  67.  
  68.         cout << ans << endl;
  69.     }
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 8752KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/djYYBw
language:
C++14 (gcc 8.3)
created:
1 day 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!