# CSES - Tree Distances I

Authors: Nathan Wang, Benjamin Qi, Abhishek Singh, Brad Ma

### Appears In

Solution 1Solution 2

## Solution 1

Described in CPH 14.3.

C++

#include <bits/stdc++.h>using namespace std;
vector<int> adj[200001];int firstMax[200001];   // to store first-max length.int secondMax[200001];  // to store second-max length.int c[200001];          // to store child for path of max length.
// calculate for every node x the maximum// length of a path that goes through a child of x

Java

### Warning!

Java exceeds the time limit on two test cases.

import java.io.*;import java.util.*;
public class TreeDistancesI {	static ArrayList<Integer>[] adj;	static int MAX_N = 200000;	static int[] firstMax = new int[MAX_N + 1];   // to store first-max length.	static int[] secondMax = new int[MAX_N + 1];  // to store second-max length.	static int[] c =	    new int[MAX_N + 1];  // to store child for path of max length.

## Solution 2

Compute a diameter of the tree as described by algorithm 2 here. Once we have a diameter $(a,b)$, output $\max(dist(a,i),dist(b,i))$ for each node $i$.

#include <bits/stdc++.h>
using namespace std;
// dist[0][i] = distance from node a to node i// dist[1][i] = distance from node b to node iint dist[2][200000];vector<int> adj[200000];
int dfs(int u, int p, int d, int i) {

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!