Advertisement
tumaryui

Untitled

Sep 4th, 2020
318
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.61 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pb push_back
  4. using namespace std;
  5.  
  6. const int N = 3e5 + 10;
  7. vector<int> gr[N];
  8.  
  9.  
  10. //dist vert
  11. pair<int,int> diam(int v, int pr = -1, int d = 0) {
  12. int bg = v;
  13. for(auto it: gr[v]) {
  14. if(it == pr) continue;
  15. pair<int,int> tmp = diam(it, v);
  16. if(tmp.first > d) {
  17. bg = tmp.second;
  18. d = tmp.first;
  19. }
  20. }
  21. return {d + 1, bg};
  22. }
  23. main() {
  24. int n;
  25. cin >> n;
  26. for(int i = 1; i < n; i++) {
  27. int l, r;
  28. cin >> l >> r;
  29. gr[l].pb(r);
  30. gr[r].pb(l);
  31. }
  32. int l = diam(1).second;
  33. int d = diam(l).first - 1;
  34. cout << d * 3 << endl;
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement