CCCPaste

CSES_Tree_Distances_I

#include <bits/stdc++.h> // Includes all standard libraries

using namespace std;

// Using long long for integer type for larger values
#define int long long

/**
* @brief Performs DFS to find the farthest node from a given start node.
* @param u Current node
* @param p Parent node
* @param dist Distance array (dist[u] = distance from root)
* @param adj Adjacency list
* @param max_dist Reference to store the maximum distance found
* @param farthest_node Reference to store the node at max_dist
*/
void find_farthest_node_dfs(int u, int p, vector<int>& dist,
const vector<vector<int>>& adj, int& max_dist,
int& farthest_node) {
dist[u] = dist[p] + 1;
for (int v : adj[u]) {
if (v != p) {
find_farthest_node_dfs(v, u, dist, adj, max_dist, farthest_node);
}
}
// Check if this node is farther than the current max
if (dist[u] > max_dist) {
max_dist = dist[u];
farthest_node = u;
}
}

/**
* @brief Performs DFS to populate distances for subtrees branching off the diameter.
* @param u Current node
* @param p Parent node (on the diameter)
* @param max_dist_to_any_node The output array being populated
* @param adj Adjacency list
*/
void populate_subtree_dists_dfs(int u, int p, vector<int>& max_dist_to_any_node,
const vector<vector<int>>& adj) {
// The distance for a subtree node is its distance from the diameter
// plus the diameter node's max distance to an endpoint.
max_dist_to_any_node[u] = max_dist_to_any_node[p] + 1;
for (int v : adj[u]) {
if (v != p) {
populate_subtree_dists_dfs(v, u, max_dist_to_any_node, adj);
}
}
}

signed main() {
// Optimize C++ streams for speed
ios::sync_with_stdio(false);
cin.tie(NULL);

int n;
cin >> n;

if (n == 1) {
cout << 0 << '\n';
return 0;
}

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

vector<int> dist_from_ep1(n + 1, 0);
int max_dist = -1;
int endpoint1 = 0;

// Use node 0 as a virtual parent with distance -1
dist_from_ep1[0] = -1;

// 1. Find one endpoint (endpoint1) of a diameter
// We start from node 1 arbitrarily
find_farthest_node_dfs(1, 0, dist_from_ep1, adj, max_dist, endpoint1);

// 2. Find the other endpoint (endpoint2) and the true diameter length
// dist_from_ep1 will now store distances from endpoint1
max_dist = -1;
int endpoint2 = 0;
find_farthest_node_dfs(endpoint1, 0, dist_from_ep1, adj, max_dist, endpoint2);

int diameter_len = max_dist;

// 3. Reconstruct the diameter path (from endpoint2 back to endpoint1)
vector<int> diameter_path;
queue<int> q;
q.push(endpoint2);

while (!q.empty()) {
int u = q.front();
diameter_path.push_back(u);
q.pop();

if (u == endpoint1) break; // Reached the other end

for (int v : adj[u]) {
// Follow the parent pointer (dist from ep1 decreases by 1)
if (dist_from_ep1[v] == dist_from_ep1[u] - 1) {
q.push(v);
break; // Found the unique parent on the path
}
}
}

// 4. Calculate max distance for every node
// This is the max distance from any node 'u' to the farthest node in the tree
// (which will always be either endpoint1 or endpoint2).
vector<int> max_dist_to_any_node(n + 1, 0);

// Set distances for the endpoints
max_dist_to_any_node[endpoint1] = diameter_len;
max_dist_to_any_node[endpoint2] = diameter_len;

int path_len = diameter_path.size();

// Iterate over internal nodes of the diameter
for (int i = 1; i < path_len - 1; i++) {
int u_on_path = diameter_path[i];

// Distance for a node on the path is its max distance to either endpoint
int dist_to_ep1 = dist_from_ep1[u_on_path];
int dist_to_ep2 = diameter_len - dist_to_ep1;
max_dist_to_any_node[u_on_path] = max(dist_to_ep1, dist_to_ep2);

// 5. Run DFS for all subtrees branching off this diameter node
for (int v_subtree : adj[u_on_path]) {
// Avoid traversing back onto the diameter
if (v_subtree != diameter_path[i - 1] && v_subtree != diameter_path[i + 1]) {
populate_subtree_dists_dfs(v_subtree, u_on_path, max_dist_to_any_node, adj);
}
}
}

// Print the result for all nodes
for (int i = 1; i <= n; i++) {
cout << max_dist_to_any_node[i] << ' ';
}
cout << '\n';

return 0;
}