fork download
copy 
  1. #include <bits/stdc++.h>
  2. using ll = long long;
  3. using ull = unsigned long long;
  4. using ld = long double;
  5. #define all(v) (v).begin(), (v).end()
  6. #define ii pair <int, int>
  7. #define FORC(i, r, a) for(int i = 1; i <= r; cin >> (a)[i++])
  8. #define FOR(i,l,r) for(int i = l; i <= r; ++i)
  9. #define FOD(i,l,r) for(int i = l; i >= r; --i)
  10. #define vi vector <int>
  11. #define mvt vector<vi>
  12. #define sz(v) (int)(v).size()
  13. #define iota(a, l, r) for(int i = l; i <= r; ++i) a[i] = i;
  14. #define taskname "TD"
  15. const long long maxN = 2e5 + 10, oo = 1e9, MOD = 1e9 + 7;
  16. using namespace std;
  17.  
  18. int dist[maxN], n, res[maxN];
  19. vector <int> adj[maxN];
  20.  
  21. void dfs(int u, int p)
  22. {
  23.     for(auto v : adj[u]) if(v != p)
  24.     {
  25.         dfs(v, u);
  26.         dist[u] = max(dist[u], dist[v] + 1);
  27.     }
  28.     res[u] = max(res[u], dist[u]);
  29. }
  30.  
  31. void dfs2(int u, int p, int len_max)
  32. {
  33.     res[u] = max(res[u], len_max);
  34.     vector <int> pre(adj[u].size() + 2, 0), suf(adj[u].size() + 2, 0);
  35.  
  36.     int id = 0;
  37.     for(auto v : adj[u]) if(v != p)
  38.     {
  39.         ++id;
  40.         pre[id] = max(pre[id - 1], dist[v] + 1);
  41.  
  42.     }
  43.  
  44.     for(auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) if(*it != p)
  45.     {
  46.         suf[id] = max(suf[id + 1], dist[*it] + 1);
  47.         --id;
  48.     }
  49.  
  50.     for(auto v : adj[u]) if(v != p)
  51.     {
  52.         ++id;
  53.         dfs2(v, u, max({pre[id - 1], suf[id + 1], len_max}) + 1);
  54.     }
  55. }
  56.  
  57. int main() {
  58. 	ios_base::sync_with_stdio(0);
  59. 	cin.tie(0); cout.tie(0);
  60. 	freopen(taskname".INP", "r", stdin);
  61. 	freopen(taskname".OUT", "w", stdout);
  62.  
  63.     cin >> n;
  64.     FOR(i,1,n - 1)
  65.     {
  66.         int u, v;
  67.         cin >> u >> v;
  68.         adj[u].push_back(v);
  69.         adj[v].push_back(u);
  70.     }
  71.  
  72.     dfs(1,0);
  73.     dfs2(1,0,0);
  74.  
  75.     FOR(i,1,n)
  76.     {
  77.         cout << res[i] << ' ';
  78.     }
  79. }
Success #stdin #stdout 0.01s 9144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UDZhvo
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!