luanaamorim

Untitled

Sep 16th, 2021
937
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <cmath>
  7. #include <iomanip>
  8. #include <map>
  9. #include <cstring>
  10. #include <set>
  11. #include <stack>
  12. #include <bitset>
  13. #define ll long long
  14. #define INF (1e9)
  15. #define MAX (int) (2e5 + 5)
  16. #define MOD 1000000007
  17. #define par pair<int, int>
  18. #define all(v) v.begin(), v.end()
  19. #define sz(x) (int) ((x).size())
  20. #define esq(x) (x<<1)
  21. #define dir(x) ((x<<1)|1)
  22. #define lsb(x) (x & -x)
  23. #define W(x) cout << #x << ": " << x << endl
  24. #define Wii(x) cout << x.first << ' ' << x.second << endl
  25. #define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  26.  
  27. using namespace std;
  28.  
  29. int dp[MAX], g[MAX], h[MAX], n, a, b, resp;
  30. vector<int> grafo[MAX];
  31.  
  32. int f(int u, int p = 0)
  33. {
  34.     int a = -INF, b = -INF;
  35.     for (int v : grafo[u])
  36.     {
  37.         if (v == p) continue;
  38.         f(v, u);
  39.         dp[u] = max(dp[u], dp[v]);
  40.         a = max(a, h[v]);
  41.         if (a > b) swap(a, b);
  42.         h[u] = max(h[u], max(g[v] + g[u] - 2, h[v] + g[u] - 2));
  43.     }
  44.  
  45.     dp[u] = max(dp[u], h[u]);
  46.     dp[u] = max(dp[u], b + g[u] - 2);
  47.     dp[u] = max(dp[u], a + b + g[u] - 4);
  48.     return dp[u];
  49. }
  50.  
  51. int main()
  52. {_
  53.     cin >> n;
  54.     for (int i = 1; i < n; i++)
  55.     {
  56.         cin >> a >> b;
  57.         grafo[a].push_back(b);
  58.         grafo[b].push_back(a);
  59.         g[a]++;
  60.         g[b]++;
  61.     }
  62.  
  63.     cout << f(1) << endl;
  64.     // for (int i = 1; i <= n; i++)
  65.     // {
  66.     //  cout << h[i] << ' ' << dp[i] << endl;
  67.     // }
  68. }
RAW Paste Data