fork download
  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
stdin
5
4 2
1 4
5 4
3 4
stdout
3
3
3
2
3