CSES - Tree Distances I
Authors: Nathan Wang, Benjamin Qi, Abhishek Singh, Brad Ma
Solution 1
Described in CPH 14.3.
#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
Solution 2
Compute a diameter of the tree as described by algorithm 2 here. Once we have a diameter , output for each node .
#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!