fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. //#include <__msvc_all_public_headers.hpp>
  4.  
  5. #pragma GCC optimize("Ofast")
  6. #pragma GCC target("avx,avx2,fma")
  7. #pragma GCC optimization ("unroll-loops")
  8.  
  9. typedef long long  ll;
  10.  
  11. #define press_F_to_pay_respect ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  12. #define forn for(int i=0;i<n;i++) 
  13. #define fore(i,a,b) for(int i = a; i < (b); i++)
  14. #define pb push_back 
  15. #define pob pop_back()
  16. #define mp make_pair 
  17. #define sc second 
  18. #define f first 
  19. #define ld long double
  20. #define kek cout<<"\n"; 
  21. #define rep(i,a,b) for(int i=a;i<b;i++)
  22. #define all(v) ((v).begin()), ((v).end()) 
  23. #define halt {cout<<"NO"; return 0;}
  24.  
  25. const ll MOD = 1e9 + 7;
  26. const ll MOD1 = 998244353;
  27. const int N = 5010;
  28. const int INF = 1e8;
  29. const ll LL_INF=1e18;
  30. const long double pi=3.1415926535;
  31. using namespace std;
  32. using namespace __gnu_pbds;
  33. typedef tree<ld,null_type,less<ld>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
  34. int divide(int a, int b)
  35. {
  36.           return (a+b-1)/b;
  37. }
  38. vector<vector<ll>> adj;
  39. vector<ll> dp;
  40. vector<ll> g;
  41. ll diam=0;
  42. vector<bool> nodes;
  43. void dfs(int s, int e)
  44. {
  45.           dp[s]=1;
  46.           vector<ll> val;
  47.           for(auto x: adj[s])
  48.           {
  49.                     if(e==x) continue;
  50.                     dfs(x,s);
  51.                     val.pb(dp[x]);
  52.           }
  53.           sort(all(val));
  54.           if(val.size()) dp[s]+=val.back();
  55.           if(val.size()>=2) g[s]=1+val.back()+val[val.size()-2];
  56.  
  57.           diam=max(diam, max(dp[s],g[s]));
  58. }
  59. void dfs1(int s, int e)
  60. {
  61.          if(adj[s].size()==1) nodes[s]=true;
  62.          for(auto x: adj[s])
  63.          {
  64.                    if(x==e) continue;
  65.                    if(dp[x]==dp[s]-1) 
  66.                    dfs1(x,s);
  67.  
  68.          }
  69. }
  70. int main()
  71. {
  72.     #if defined(_DEBUG)
  73. 	freopen("input.txt", "r", stdin);
  74. 	freopen("output.txt", "w", stdout);
  75.     #endif
  76.  press_F_to_pay_respect;
  77.  // cout << fixed << setprecision(12) << ans;
  78.  // string al = "abcdefghijklmnopqrstuvwxyz";
  79.  int questions=1;
  80.  // cin>>questions;
  81.  while(questions--)
  82.  {
  83.            int n;
  84.        cin>>n;
  85.        if(n==1)
  86.        {
  87.                  cout<<1;
  88.                  return 0;
  89.        }
  90.      adj.resize(n+2);
  91.      dp.resize(n+2);
  92.      g.resize(n+2);
  93.      nodes.resize(n+2);
  94.      int z=n-1;
  95.      while(z--)
  96.      {
  97.                int a,b;
  98.                cin>>a>>b;
  99.                adj[a].pb(b);
  100.                adj[b].pb(a);
  101.      }
  102.      dfs(1,0);
  103.      vector<ll> d=dp;
  104.      // we have found diam == tree diameter 
  105.      for(int i=1;i<=n;i++)
  106.      {
  107.                if(g[i]==diam)
  108.                {
  109.                          dp.clear();
  110.                          dp.resize(n+2);
  111.                          g.clear();
  112.                          g.resize(n+2);
  113.                          // now lets root the tree on node i and count dp and g vectors
  114.                          dfs(i,0);
  115.                          vector<int> val;
  116.                          // add in vector<int> val all dp values from other nodes
  117.                          for(auto x: adj[i]) val.pb(dp[x]);
  118.                          // then choose two maximum
  119.                          sort(all(val));
  120.                          int mx=val.back();
  121.                          int mx1=val[val.size()-2];
  122.                          // then do dfs1 to find leaves 
  123.                          for(auto x: adj[i])
  124.                          {
  125.                                    if(dp[x]==mx || dp[x]==mx1) dfs1(x,0);
  126.                          }
  127.                          // if we have found needed nodes write them
  128.                }
  129.      }
  130.      dp=d;
  131.      // otherwise the tree is rooted in node 1 and we need to find leaves from here
  132.      for(int i=1;i<=n;i++)
  133.      {
  134.                if(dp[i]==diam)
  135.                {
  136.                          // dfs from node i
  137.                          //cout<<"aaa1"<<" "<<i;
  138.                          nodes[i]=true;
  139.                          dfs1(i,0);
  140.                          break;
  141.                }
  142.      }
  143.      // we have found the answer, print it
  144.      for(int i=1;i<=n;i++)
  145.      {
  146.                if(nodes[i]) cout<<diam;
  147.                else cout<<diam-1;
  148.                kek;
  149.      }
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  }
  159.  
  160.  
  161.  
  162.  
  163.  // !!! LOOK AT NUMBER OF QUESTIONS IN A PROBLEM !!! (cin>>questions)
  164.  
  165.  
  166.  
  167.   // cout <<"Runtime is:"<<clock() * 1.0 / CLOCKS_PER_SEC <<endl;
  168.    return 0;
  169.  
  170.  
  171.  
  172. }
Success #stdin #stdout 0s 4792KB
comments (?)
stdin
copy 
5
4 2
1 4
5 4
3 4
stdout
copy 
3
3
3
2
3
https://ideone.com/dd5gOx
language:
C++14 (gcc 8.3)
created:
3 years 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!