cpc/Tree_DistancesI.cpp at main · Mibrahim111/cpc · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
const int N = 200004;
#define INF (ll)1e18+5

int dp[N]={}, ans[N]={};
vector<int> adj[N];

void dfs1(int v,int p){
  dp[v] = 0;

  for(int ne : adj[v]){
    if(ne != p){
      dfs1(ne,v);
      dp[v] = max(dp[v],dp[ne]+1);
    }
  }
}

void dfs2(int v,int p, int up){
  ans[v] = max(dp[v],up);

  int mx1 = -1, mx2 = -1;
  for(int i : adj[v]){
    if(i == p) continue;
    int d = dp[i] + 1;
    if(mx1 < d){mx2 = mx1 , mx1 = d;}
    else if(mx2 < d){mx2 = d;}
  }

  for(int i : adj[v]){
    if(p == i) continue;
    int take = (1 + dp[i] == mx1 ? mx2 : mx1);

    dfs2(i,v,max(1+up,1 + take));
  }
}


void solve(){

  int n;
  cin>>n;

  for(int i = 1,u,v;i < n;++i){
    cin>>u>>v;
    adj[v].push_back(u);
    adj[u].push_back(v);
  }
  dfs1(1,0);
  dfs2(1,0,0);

  for(int i = 1;i <= n;++i)
  {
    cout << ans[i] << ' ';
  }

}


int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    #ifndef ONLINE_JUDGE
    freopen("input.txt","rt",stdin);
    #endif

    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}