CSES - Tree Distances I

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

Table of Contents

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)(a,b), output max(dist(a,i),dist(b,i))\max(dist(a,i),dist(b,i)) for each node ii.

#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 i
int 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!