Maruf_Hasan

Diameter of a tree

Apr 26th, 2021
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.17 KB | None | 0 0
  1.  
  2. //In the Name of Allah Most Gracious, Most Merciful//
  3. /*If you want something you've never had, you have to do something you never did.*/
  4.  
  5. #include<bits/stdc++.h>
  6. #include<ext/pb_ds/assoc_container.hpp>
  7. #include<ext/pb_ds/tree_policy.hpp>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11.  
  12.  
  13.  
  14.  
  15.  
  16. #define pb push_back
  17. #define ll long long
  18. #define pii pair<int,int>
  19. #define pll pair<ll,ll>
  20. #define MaxN 201007
  21. #define INF 1e9
  22. #define INFL 1e18
  23. #define PI acos(-1)
  24. #define mp make_pair
  25.  
  26. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
  27.  
  28. //const int fx[]= {+1,-1,+0,+0};
  29. //const int fy[]= {+0,+0,+1,-1};
  30. //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
  31. //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
  32. //const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
  33. //const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
  34.  
  35.  
  36. int gcd(int a, int b)
  37. {
  38. return b ? gcd(b, a%b) : a;
  39. }
  40.  
  41. ll bigmod(ll b,ll p,ll m)
  42. {
  43. ll res=1LL%m;
  44. ll x=b%m;
  45. while(p)
  46. {
  47. if( p & 1LL )res=(res*x) % m;
  48. x=(x*x)%m;
  49. p >>=1LL;
  50. }
  51. return res;
  52. }
  53.  
  54. int n;
  55. vector<int>adj[2*MaxN];
  56. int d,node;
  57. bool visited[2*MaxN];
  58.  
  59.  
  60. void dfs(int x,int dis)
  61. {
  62. visited[x]=true;
  63. if(dis>d)
  64. {
  65. d=dis;
  66. node=x;
  67. }
  68. for(int i=0;i<adj[x].size();i++)
  69. {
  70. int v=adj[x][i];
  71.  
  72. if(visited[v]==false)
  73. {
  74. dfs(v,dis+1);
  75. }
  76. }
  77. }
  78.  
  79.  
  80. int main()
  81. {
  82.  
  83. // #ifndef ONLINE_JUDGE
  84. // freopen("input.txt","r",stdin);
  85. // freopen("output.txt","w",stdout);
  86. // #endif
  87. ios_base::sync_with_stdio(false);
  88. cin.tie(NULL);
  89. cin>>n;
  90. for(int i=1;i<n;i++)
  91. {
  92. int x,y;
  93. cin>>x>>y;
  94. adj[x].pb(y);
  95. adj[y].pb(x);
  96. }
  97. d=0;
  98. node=0;
  99. dfs(1,0);
  100. memset(visited,false,sizeof visited);
  101. dfs(node,0);
  102. cout<<d<<endl;
  103.  
  104.  
  105. //#ifdef LOCAL_DEFINE
  106. // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  107. // #endif
  108. ///Before submit=>
  109. /// *check for integer overflow,array bounds
  110. /// *check for n=1
  111. }
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
Advertisement
Add Comment
Please, Sign In to add comment