SHARE
TWEET

Untitled

Misbah_Uddin_Tareq Jan 24th, 2020 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define pb push_back
  5. const ll mx=30005;
  6.  
  7. ll vis[mx],dis[mx];
  8. vector<pair<ll,ll>>adj[mx];
  9. ll maxi=0;
  10. int p=0;
  11.  
  12. void dfs(ll s)
  13. {
  14.     vis[s]=1;
  15.  
  16.     for(auto it:adj[s])
  17.     {
  18.         if(!vis[it.first])
  19.         {
  20.             dis[it.first]=dis[s]+it.second;
  21.             if(dis[it.first]>maxi)
  22.             {
  23.                  maxi=dis[it.first];
  24.                  p=it.first;
  25.             }
  26.  
  27.             dfs(it.first);
  28.         }
  29.     }
  30. }
  31.  
  32. int main()
  33. {
  34.     ll t;
  35.     scanf("%lld",&t);
  36.  
  37.     for(ll tc=1; tc<=t; tc++)
  38.     {
  39.         ll n;
  40.         scanf("%lld",&n);
  41.  
  42.         for(int i=1; i<n; i++)
  43.         {
  44.             ll u,v,w;
  45.             scanf("%lld %lld %lld",&u,&v,&w);
  46.             adj[u].pb({v,w});
  47.             adj[v].pb({u,w});
  48.         }
  49.  
  50.         memset(vis,0,sizeof vis);
  51.         memset(dis,0,sizeof dis);
  52.         maxi=0;
  53.         dfs(0);
  54.  
  55.         cout<<p<<endl;
  56.  
  57.         memset(vis,0,sizeof vis);
  58.         memset(dis,0,sizeof dis);
  59.         maxi=0;
  60.         dfs(p);
  61.  
  62.  
  63.         printf("Case %lld: %lld\n",tc,maxi);
  64.  
  65.         for(int i=0; i<=mx; i++)
  66.         {
  67.             adj[i].clear();
  68.         }
  69.     }
  70.  
  71.     return 0;
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top