CSES - Tree Distances I

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

Edit This Page

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!

Join Forum