Untitled
TEXT
views 14
,
size 1949 b
``````#include <bits/stdc++.h>
using namespace std;
const int MAX_NODES = 100005;
int in[MAX_NODES];
int out[MAX_NODES];
vector<int> v[1000005];
int n;
void dfs1( int u, int parent)
{
// initially every node has 0 height
in[u] = 0;

// traverse in the subtree of u
for (int child : v[u]) {

// if child is same as parent
if (child == parent)
continue;

// dfs called
dfs1( child, u);

// recursively calculate the max height
in[u] = max(in[u], 1 + in[child]);
}
}

// function to pre-calculate the array ouut[]
// which stores the maximum height when traveled
// via parent
void dfs2( int u, int parent)
{
// stores the longest and second
// longest branches
int mx1 = -1, mx2 = -1;

// traverse in the subtress of u
for (int child : v[u]) {
if (child == parent)
continue;

// compare and store the longest
// and second longest
if (in[child] >= mx1) {
mx2 = mx1;
mx1 = in[child];
}

else if (in[child] > mx2)
mx2 = in[child];
}

// traverse in the subtree of u
for (int child : v[u]) {
if (child == parent)
continue;

int longest = mx1;

// if longest branch has the node, then
// consider the second longest branch
if (mx1 == in[child])
longest = mx2;

// recursively calculate out[i]
out[child] = 1 + max(out[u], 1 + longest);

// dfs function call
dfs2( child, u);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++)
{
cout<<in[i]+out[i]<<"\n";
}
return 0;
}``````